Problem Description

You have an unrooted tree with $n$ nodes, numbered from $1$ to $n$. The distance $\operatorname{dis}(i, j)$ between two points on the tree is defined as the number of edges on the simple path from node $i$ to node $j$.

There are $k$ key points $a_1, a_2, \ldots, a_k$. For each node, we want to determine which key point is the closest to it. Specifically, for a node $v$, let $f(v)$ denote the index $i$ such that $\operatorname{dis}(v, a_i)$ is minimized. If there are multiple such $i$, we choose the smallest $i$.

We are given $f(1), f(2), \ldots, f(n)$, and we need to find out how many possible sets of $(a_1, a_2, \ldots, a_k)$ satisfy these conditions. Since the answer may be very large, output the result modulo $998244353$.

Input Format

Multiple test cases are provided. The first line contains an integer $T$ representing the number of test cases.
For each test case, the first line contains two integers $n$ and $k$, representing the number of nodes and the number of key points, respectively.
The next $n - 1$ lines each contain two integers $u$ and $v$, representing an edge in the tree.
The following line contains $n$ integers, $f(1), f(2), \ldots, f(n)$. Note: The data does not guarantee that there exists a valid set of $(a_1, a_2, \ldots, a_k)$.

Output Format

For each test case, output an integer representing the answer modulo $998244353$.

Sample Input and Output

Sample Input #1

3
3 3
1 2
2 3
1 2 1
3 2
1 2
2 3
1 2 2
3 2
1 2
2 3
2 1 1

Sample Output #1

0
1
2

Sample Input #2

1
10 5
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 1 2 2 3 3 4 4 5 5

Sample Output #2

13

Notes

[Sample #1 Explanation]

In the first sample, for the second set of data, one solution is $(1, 2)$. For the third set of data, two solutions are $(2, 1)$ and $(3, 1)$.

Note that when multiple points have the same distance, we choose the smallest $i$ rather than the smallest $a_i$.

[Sample #3]

See the attached files voronoi/voronoi3.in and voronoi/voronoi3.ans. This sample meets the constraints of test points $3 \sim 4$.

[Sample #4]

See the attached files voronoi/voronoi3.in and voronoi/voronoi3.ans. This sample meets the constraints of test points $7 \sim 10$.

[Data Range]

For all data, it is guaranteed that $1 \le T \le 10$, $2 \le k \le n \le 3 \times 10^3$, and $1 \le f(i) \le k$.

The specific constraints are as follows:

Special Property A: The tree is a chain.
Special Property B: $k = 2$.

见题面 Input 部分

见题面 Output 部分