Problem Description

There is a tree with $n$ nodes and $n-1$ edges that make all nodes connected. Each node $i$ has a $\textbf{distinct}$ weight $a_i$. A monkey is jumping on the tree. In one jump, the monkey can jump from node $u$ to node $v$ if and only if $a_v$ is the greatest of all nodes on the shortest path from node $u$ to node $v$. The monkey will stop jumping once no more nodes can be reached.

For each integer $k \in [1, n]$, calculate the maximum number of nodes the monkey can reach if he starts from node $k$.

Input

The first line of the input contains an integer $T$ $(1 \leq T \leq 10^4)$, representing the number of test cases.

The first line of each test case contains an integer $n$ $(1 \leq n \leq 10^5)$, representing the number of nodes.

Each of the following $n - 1$ lines contains two integers $u, v$ $(1 \leq u, v \leq n)$, representing an edge connecting node $u$ and node $v$. It is guaranteed that the input will form a tree.

The next line contains $n$ $\textbf{distinct}$ integers $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^9)$, representing the weight of each node.

It is guaranteed that the sum of $n$ over all test cases does not exceed $8 \times 10^5$.

Output

For each test case, output $n$ lines. The $k$-th line contains an integer representing the answer when the monkey starts from node $k$.

2
3
1 2
2 3
1 2 3
5
1 2
1 3
2 4
2 5
1 4 2 5 3

3
2
1
4
2
3
1
3

Hint

For the second case of the sample, if the monkey starts from node $1$, he can reach at most $4$ nodes in the order of $1 \to 3 \to 2 \to 4$.