题目翻译洛谷

题面翻译

题目描述

树中两个顶点 $u$ 和 $v$ 之间的距离是指顶点 $u$ 到顶点 $v$ 必须经过的最小边数。

亚历克斯的生日快到了，蒂莫菲想送他一棵有 $n$ 个顶点的树。然而，亚历克斯是个喜怒无常的孩子。在 $q$ 天里，他每天都会选择一个整数，第 $i$ 天选择的整数用 $d_i$ 表示。如果在第 $i$ 天，树上没有两片距离正好为 $d_i$ 的叶子节点，亚历克斯就会很失望。

蒂莫菲决定送给亚历克斯一个设计器，这样他就可以随心所欲地改变他的树了。蒂莫菲知道亚历克斯也很懒惰，所以每天一开始，他可以进行多次以下类型的操作：

• 选择顶点 $u$ 、 $v_1$ 和 $v_2$，需要满足 $u$ 和 $v_1$ 之间有一条边， $u$ 和 $v_2$ 之间没有边。然后删除 $u$ 和 $v_1$ 之间的边，并在 $u$ 和 $v_2$ 之间添加一条边。如果操作后图形不再是树，则不能执行此操作。

不知怎的，蒂莫菲设法找出了所有的 $d_i$ 。之后，他又想出了一个绝妙的主意——以防万一，为这组集合 $d_i$ 制作一本说明书，这样亚历克斯就不会失望了。

输入格式

第一行包含整数 $t$（$1\leq t\leq100$），表示数据组数。

每个测试用例的第一行包含两个整数 $n$（$3\leq n\leq500$）和 $q$（$1\leq q\leq500$），分别表示树中的节点数和操作天数。

下面第 $q$ 行的第 $i$ 行包含整数 $d_i$（$2\leq d_i\leq n-1$）。

保证 $\sum n,\sum q\le500$。

可以证明，满足所述条件的树和操作序列总是存在的。

输出格式

对于每组数据，首先输出描述树的 $n-1$ 条边。如果节点 $u$ 和 $v$ 之间有一条边，则必须输出 $u\ v$ 或 $v\ u$。

在接下来的 $q$ 行中，每行输出三个整数 $u$、$v_1$、$v_2$。如果亚历克斯这天不需要执行操作，则直接输出 $\texttt{-1 -1 -1}$。