Note the **unusual memory limit** for this problem.
Given a rooted tree with $\textstyle n$ nodes and $\textstyle n-1$ edges. The $\textstyle i$\-th edge can be described by $\textstyle (a_i, b_i)$, which represents an edge connecting node $\textstyle a_i$ and node $\textstyle b_i$, where node $\textstyle a_i$ is the parent of node $\textstyle b_i$.
There are $\textstyle n-1$ queries. The $\textstyle i$\-th query contains an integer $\textstyle c_i$, asking for the length of the longest simple path starting from node $\textstyle c_i$ in the graph (forest) formed by the first $\textstyle i$ edges. **It is guaranteed that there does not exist $\textstyle j$ such that $\textstyle 1 \leq j \leq i$ and $\textstyle b_j = c_i$, i.e., $\textstyle c_i$ is the root of a tree in the forest.**
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $\textstyle t$ ($\textstyle 1 \leq t \leq 10^5$). The description of the test cases follows.
The first line of each test case contains an integer $\textstyle n$ ($\textstyle 2 \leq n \leq 10^6$), representing the number of nodes in the tree.
The next $\textstyle n-1$ lines each contain three integers $\textstyle a_i, b_i, c_i$ ($\textstyle 1 \leq a_i, b_i, c_i \leq n, a_i \neq b_i$), representing that the parent of node $\textstyle b_i$ is $\textstyle a_i$, and the $\textstyle i$\-th query is $\textstyle c_i$.
It is guaranteed that:
- For each test case, the $\textstyle n-1$ edges form a rooted tree.
- For each test case, for any $\textstyle 1 \leq i \leq n-1$, there does not exist $\textstyle j$ such that $\textstyle 1 \leq j \leq i$ and $\textstyle b_j = c_i$.
- The sum of $\textstyle n$ over all test cases does not exceed $\textstyle 10^6$.
输出格式
For each test case, output $\textstyle n-1$ integers in one line. The $\textstyle i$\-th integer represents your answer to the $\textstyle i$\-th query.