Problem Description

Maddy got lost in the forest..., and she saw a strange tree.
In front of her is a tree of size $n$, which is an undirected, acyclic, connected graph $T$ with $n$ vertices and $n-1$ edges.
However, when Maddy was not paying attention, the shape of the tree changed: a newly grown branch connected two different non-adjacent vertices! That is, the tree $T$ became an undirected connected graph $G'$ with $n$ vertices and $n$ edges.
To test you, Maddy gives the original shape of the tree and the values $\sum D_i$ for all vertices, where $\sum D_i$ is the sum of distances from vertex $i$ to every other vertex in the new graph $G'$, i.e., $\sum D_i = \sum_{j \in V} D_{G'}(i, j)$.
You need to tell Maddy which two vertices are connected by the newly grown branch.

Input Format

The first line contains an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases.
For each test case, the first line contains an integer $n$ ($3 \le n \le 10^5$), indicating the number of vertices in the graph.
Then follow $n-1$ lines, each containing two integers $u$ and $v$ ($1 \le u, v \le n, u \ne v$), indicating that there is an edge between $u$ and $v$ in the tree $T$.
Then one line contains $n$ integers $\sum D_1, \sum D_2, \dots, \sum D_n$, representing for each vertex the sum of distances to all other vertices in $G'$.
It is guaranteed that across all test cases, $\sum n \le 3 \times 10^5$. Also, in each test case the input graph forms a tree, and the two endpoints of the hidden edge are distinct and non-adjacent in the original graph.

Output Format

For each test case, output one line with two integers $x$ and $y$, indicating the two vertices connected by the newly grown branch.
If there are multiple valid answers, you may output any one of them. (For example, if $1\ 2$ is valid, then $2\ 1$ is also valid.)

1
7
1 2
1 3
2 4
2 5
3 6
3 7
10 10 10 11 15 15 11

4 7

Hint

Explanation for Sample 1

The following figure shows the shape of $G'$.

:::align{center} :::

Hint

The distance $D_{i,j}$ in the graph is defined as the minimum number of edges among all paths starting from $i$ and ending at $j$.

Translated by ChatGPT 5