Critical Distances - Repovive Opening Round | Repovive

0G. Critical Distances

3500 pts2s256 MB

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

Input

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

Output

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

Where each answer is the count modulo $998244353$ .

Samples

Input

Explanation

Sample test case

Output

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$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

0G. Critical Distances

Input

Output

Samples

0G. Critical Distances

Constraints

Input

Output

Samples

Constraints