M. LIS On Tree
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There were too many constructive problems in this contest, so we decided to set a standard data structure problem.

You are given a tree with $$$n$$$ labeled nodes. Each node also has a blank value initially.

The longest increasing tree subsequence between two nodes $$$(u, v)$$$ on the tree is computed as follows:

  • Write down all the nonblank values from the nodes on the path from $$$u$$$ to $$$v$$$, in order. Compute the longest increasing subsequence$$$^\dagger$$$ of the resulting sequence.

You are given $$$n$$$ updates, $$$x_1, x_2 \dots x_n$$$. For update $$$i$$$, fill in the value $$$i$$$ at node $$$x_i$$$. After each update, compute the longest longest increasing tree subsequence among all pairs of nodes $$$(u, v)$$$ in the tree.

It is guaranteed that all $$$x_i$$$ values are distinct.

$$$^\dagger$$$ Define a sequence of integers $$$a_i...a_m$$$. A subsequence $$$a_{i_1}, a_{i_2}, ..., a_{i_k}$$$ where $$$1 \leq i_1 \lt i_2 \lt \cdots \lt i_k \leq m$$$ is called increasing if $$$a_{i_1} \lt a_{i_2} \lt a_{i_3} \lt ... \lt a_{i_k}$$$. An increasing subsequence is called longest if it has maximum length among all increasing subsequences.

Input

The first line of the input contains an integer $$$1 \leq t \leq 10^4$$$, denoting the number of test cases.

The first line of each test case contains one integer $$$2 \leq n \leq 5 \cdot 10^5$$$.

The next $$$n - 1$$$ lines contain two integers $$$1 \leq u, v \leq n$$$, denoting an undirected edge between the nodes with labels $$$u$$$ and $$$v$$$, respectively. It is guaranteed that the input edges form a tree.

The last line of input for the testcase consists of $$$n$$$ integers $$$x_1...x_n$$$, denoting the updates in order. It is guaranteed that all $$$x_i$$$ values are distinct.

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

Output

For each test case, print $$$n$$$ space-separated integers on a single line, denoting the answer after the $$$i^\textrm{th}$$$ update.

Example
Input
4
5
1 2
2 3
3 4
4 5
3 1 5 2 4
10
5 1
3 4
3 6
3 7
8 3
5 8
2 5
9 2
9 10
3 6 9 4 5 2 1 8 10 7
15
10 1
3 4
13 5
3 7
8 3
15 8
12 13
9 12
2 9
11 2
11 14
6 11
10 6
10 15
9 2 10 5 13 14 7 15 11 12 1 6 8 3 4
2
1 2
1 2
Output
1 2 2 2 3
1 2 2 2 2 3 3 3 4 4
1 2 3 3 3 3 4 4 4 4 4 4 5 6 7
1 2
Note

Remember that the updates tell you the value of the $$$x_i^\textrm{th}$$$ node, not that the value of node $$$i$$$ is $$$x_i$$$.

An example of the process for the first tree is shown below. The yellow nodes are one potential longest increasing tree subsequence after each operation. The node's labels are 1-5 from left to right, initially with blank values.