Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/4/problems/G

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/4/problems/G

Repovive

You are given a tree with $n$ vertices labeled $1$ to $n$ . Vertices $1,2,\ldots,k$ are critical.

Choose any non-empty subset $S \subseteq \{1,\ldots,n\}$ .

For each $v \in \{1,\ldots,k\}$ define $d_v=\min_{u\in S} \operatorname{dist}(v,u),$ where $\operatorname{dist}(x,y)$ is the number of edges on the (unique) path between $x$ and $y$ in the tree.

Thus each choice of $S$ produces a sequence $(d_1,d_2,\ldots,d_k)$ . Count how many distinct sequences can appear over all non-empty $S$ , and output the answer modulo $998244353$ .

Constraints

$1 \le t \le 100$
$1 \le n \le 1000$
$1 \le k \le n$
$\sum n \le 1000$ over all test cases

t \\[0.5em] \left. \begin{array}{l} n \quad k \\ v_1 \quad u_1 \\ \vdots \\ v_{n-1} \quad u_{n-1} \end{array} \right\} \times t

\begin{array}{l} ans_1 \\ \vdots \\ ans_t \end{array}

Where each answer is the count modulo $998244353$ .

4G. Critical Distances

Constraints

Input

Output

Samples

Constraints