题目描述

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

你需要向 $G$ 中添加零条或多条边。添加一条连接顶点 $i$ 和顶点 $j$ 的边的代价为 $W_i + W_j$。

请输出满足最小总代价条件的添加边方案中的一种。

• $G$ 是 $2$-顶点连通的。换句话说，对于 $G$ 中的每个顶点 $v$，从 $G$ 中移除 $v$ 及其相关的边后，$G$ 仍然是连通的。

你需要解决 $T$ 个测试用例。

约束条件

• $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$。

输入

从标准输入读入数据，数据格式如下，这里 $\\mathrm{case}_i$ 表示第 $i$ 个测试用例：

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

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

$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
1 3
2
7 6
1 5

在第一个测试用例中，添加一条连接顶点 $1$ 和顶点 $3$ 的边可以使 $G$ 满足问题描述中的条件。
这样需额外花费 $W_1 + W_3 = 2 + 5 = 7$。没有比 $7$ 更小代价的添加边方案，所以这是一个有效的解决方案。

在第二个测试用例中，上述解决方案的总代价为 $(W_7 + W_6) + (W_1 + W_5) = 1100000 + 10001 = 1110001$，这是可能的最小代价。