Description

给定一棵包含 $n$ 个顶点和 $n-1$ 条边的树。需要在这棵树上添加恰好 $m$ 条新边。不允许添加重边或自环。如果某个顶点在添加边之前的度数为 $t_i$，那么在添加边之后，其度数不得超过 $t_i + k$。注意顶点的度数是指与其相连的边的数量。

此外，给定 $m+n-1$ 个整数 $a_1, a_2, \dots, a_{m+n-1}$。添加边后，需要为每条边分配数组 $a$ 中的一个元素，且每个数组元素恰好对应一条边。分配给边的值 $a_i$ 表示其权重。

需要以如下方式添加新边并为边分配数值：使得所有顶点对之间的最短距离之和 最大化。即需要最大化函数 $\sum d_{ij}$，其中 $d_{ij}$ 是顶点 $i$ 和 $j$（$1 \leq i < j \leq n$）之间的最小距离。顶点之间的最小距离是指它们之间简单路径上所有边的权重之和。

请注意，本题不需要提交代码，而是需要提交实际答案。你可以访问所有测试数据。

Input Format

共有 $5$ 个测试用例。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n \leq 5\,000$，$1 \leq m \leq 250\,000$，$1 \leq k \leq 500$）——树中的顶点数量、需要添加的边数以及每个顶点可以添加的最大边数。

第二行包含 $m+n-1$ 个整数 $a_1, a_2, \dots, a_{m+n-1}$（$1 \leq a_i \leq 10^6$）。

接下来的 $n-1$ 行，每行包含两个整数 $v_i$ 和 $u_i$（$1 \leq v_i, u_i \leq n$）——表示初始树中相连的顶点编号。保证初始给定的图是一棵树。

保证总能以符合题目要求的方式添加边。

Output Format

对于每个测试用例，输出以下内容：

如果你有该测试用例的答案，输出 $1$，否则输出 $0$。

如果有答案，则在接下来的 $m+n-1$ 行中，每行输出三个整数 $v_i$、$u_i$ 和 $a_i$——表示最终图中相连的顶点编号及其边的权重。

Hint

设 $d_0$ 是测试用例中的某个基准值，$d$ 为你的图中所有顶点对距离之和。如果 $d > d_0$，你将获得该测试用例的 $20$ 分。否则，你将获得的分数为：

如果 $s$ 是所有测试用例得分的总和，则本次提交将获得四舍五入后的整数 $s$ 分。