题目描述

给定一棵有 $N$ 个顶点的无向树 $G$。$G$ 的所有顶点的度数都不超过 $3$。
顶点编号为 $1$ 到 $N$。边编号为 $1$ 到 $N-1$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。
此外，每个顶点都有一个权值，第 $i$ 个顶点的权值为 $W_i$。

你可以在 $G$ 上添加 $0$ 条或多条边。若在顶点 $i$ 和顶点 $j$ 之间添加一条边，则需要花费 $W_i + W_j$ 的代价。

请输出一种添加边的方法，使得满足以下条件，并且总代价最小：

• $G$ 是二重顶点连通的。也就是说，对于 $G$ 中任意一个顶点 $v$，即使将 $v$ 及其所有相邻的边从 $G$ 中移除，$G$ 依然保持连通。

给定 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入以如下格式从标准输入给出，其中 $\mathrm{case}_i$ 表示第 $i$ 个测试用例。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例的输入格式如下：

$N$
$W_1\ W_2\ \dots\ W_N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{N-1}\ v_{N-1}$

输出格式

对于每个测试用例，输出如下格式的答案。设：

• 需要添加的边数为 $M$，
• 第 $i$ 条添加的边连接顶点 $a_i$ 和顶点 $b_i$。

如果有多种方案都能达到最小总代价，输出任意一种即可。

$M$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$
$a_M\ b_M$

样例 1

输入

2
3
2 3 5
1 2
2 3
7
1 10 100 1000 10000 100000 1000000
1 2
2 3
2 4
3 5
3 6
4 7

输出

1
1 3
2
7 6
1 5

说明/提示

限制条件

• $1 \leq T \leq 2 \times 10^5$
• $3 \leq N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• 输入给定的图是树
• 输入给定的图中所有顶点的度数不超过 $3$
• $1 \leq W_i \leq 10^9$
• $W_i$ 是整数
• 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$

样例解释 1

在第 $1$ 个测试用例中，连接顶点 $1$ 和顶点 $3$ 可以使 $G$ 满足题目要求。此时总代价为 $W_1 + W_3 = 2 + 5 = 7$。不存在总代价小于 $7$ 且满足条件的方案，因此这是最优解。
在第 $2$ 个测试用例中，总代价为 $(W\_7 + W\_6) + (W\_1 + W\_5) = 1100000 + 10001 = 1110001$，这是最小的。

由 ChatGPT 4.1 翻译