G. Awkward Nodes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree consisting of $$$N$$$ nodes numbered from $$$1$$$ to $$$N$$$, connected by $$$N-1$$$ edges.

You are also given a list of $$$M$$$ distinct "special" nodes. The remaining $$$N-M$$$ nodes are "normal."

You can move between nodes along the tree edges.

  • Normal nodes can be visited any number of times.
  • Each special node can be visited at most once during your entire journey.

For each node $$$i$$$ $$$(1 \le i \le N)$$$, determine the maximum number of distinct nodes that can be visited in a single continuous journey starting from node $$$i$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 2 \cdot 10^5$$$), the number of test cases. The description of each test case follows:

  • The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le M \le N \le 2 \cdot 10^5$$$).
  • The second line contains $$$M$$$ distinct integers $$$s_1, \dots, s_M$$$ ($$$1 \le s_i \le N$$$), the special nodes.
  • The next $$$N-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N$$$), denoting an edge.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print $$$N$$$ space-separated integers, where the $$$i$$$-th integer is the answer for a starting journey from node $$$i$$$.

Example
Input
2
3 1
2
1 2
2 3
3 1
1
1 2
1 3
Output
3 2 3
2 3 3
Note

Test Case 1:

  • Start at $$$1$$$: The journey $$$1 \to 2 \to 3$$$ is valid. Maximum number of unique nodes visited: $$$3$$$.
  • Start at $$$2$$$ (Special): The journey can be $$$2 \to 1$$$ or $$$2 \to 3$$$. A journey like $$$2 \to 1 \to 2 \to 3$$$ is invalid as it requires revisiting node 2. Maximum number of unique nodes visited: $$$2$$$.
  • Start at $$$3$$$ (Normal): The journey $$$3 \to 2 \to 1$$$ is valid. Maximum number of unique nodes visited: $$$3$$$.