题目描述

Maddy 在树林里迷路了……，她看到了一棵奇特的树。
在她面前是一个大小为 $n$ 的树，这是一个由 $n$ 个顶点 $n-1$ 条边组成的无向无环连通图 $T$。
但是 Maddy 一不留神，树的形态发生了改变，有两个不相邻的不同顶点之间通过了一条新生的枝丫连了起来！也就是说，树 $T$ 变成了一个由 $n$ 个顶点 $n$ 条边组成的无向连通图 $G'$。
Maddy 为了考验你，她给出了原本树的形态以及所有顶点的 $\sum D_i$，其中 $\sum D_i$ 为顶点 $i$ 在这个新的图 $G'$ 上到每一个其他顶点的距离之和，也即 $\sum D_i = \sum_{j \in V} D_{G'}(i, j)$。
你需要告诉 Maddy 新生枝丫所连接的两点。

输入格式

第一行输入一个整数 $T$ ($1 \le T \le 10^5$)，表示数据组数。
每组测试数据输入的第一行输入一个整数 $n$ ($3 \le n \le 10^5$)，表示图的顶点数量。
随后 $n-1$ 行每行输入两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \ne v$)，表示树 $T$ 上存在一条 $u$ 到 $v$ 的边。
随后一行输入 $n$ 个整数 $\sum D_1, \sum D_2, \dots, \sum D_n$ 分别表示在 $G'$ 上每个顶点到其他顶点的距离之和。
保证所有测试数据输入中的 $\sum n \le 3 \times 10^5$，且每组数据输入的图构成一棵树，所隐藏的边的两点在原图上不同且不相邻。

输出格式

每组测试数据输出一行两个整数 $x$ 和 $y$，表示新生枝丫所连的两个顶点。
如果有多个合法的答案则你可以输出其中任意一个。（例如 1 2 合法时 2 1 也合法）

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

4 7

提示

样例 1 解释

下面的图展示了 $G'$ 的形态。

:::align{center} :::

提示

图上两点的距离 $D_{i,j}$ 定义为所有从 $i$ 开始到 $j$ 结束的路径中经过边数的最小值。