Maddy 在树林里迷路了……，她看到了一棵奇特的树。 在她面前是一个大小为 的树，这是一个由 个顶点 条边组成的无向无环连通图 。 但是 Maddy 一不留神，树的形态发生了改变，有两个不相邻的不同顶点之间通过了一条新生的枝丫连了起来！也就是说，树 变成了一个由 个顶点 条边组成的无向连通图 。 Maddy 为了考验你，她给出了原本树的形态以及所有顶点的 ，其中 为顶点 在这个新的图 上到每一个其他顶点的距离之和，也即 。 你需要告诉 Maddy 新生枝丫所连接的两点。
第一行输入一个整数 ()，表示数据组数。 每组测试数据输入的第一行输入一个整数 ()，表示图的顶点数量。 随后 行每行输入两个整数 和 ()，表示树 上存在一条 到 的边。 随后一行输入 个整数 分别表示在 上每个顶点到其他顶点的距离之和。 保证所有测试数据输入中的 ，且每组数据输入的图构成一棵树，所隐藏的边的两点在原图上不同且不相邻。
每组测试数据输出一行两个整数 和 ，表示新生枝丫所连的两个顶点。 如果有多个合法的答案则你可以输出其中任意一个。（例如 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
下面的图展示了 的形态。
:::align{center} :::
图上两点的距离 定义为所有从 开始到 结束的路径中经过边数的最小值。
:::