CF1899F.Alex's whims

Tree is a connected graph without cycles. It can be shown that any tree of $n$ vertices has exactly $n - 1$ edges.

Leaf is a vertex in the tree with exactly one edge connected to it.

Distance between two vertices $u$ and $v$ in a tree is the minimum number of edges that must be passed to come from vertex $u$ to vertex $v$.

Alex's birthday is coming up, and Timofey would like to gift him a tree of $n$ vertices. However, Alex is a very moody boy. Every day for $q$ days, he will choose an integer, denoted by the integer chosen on the $i$-th day by $d_i$. If on the $i$-th day there are not two leaves in the tree at a distance exactly $d_i$, Alex will be disappointed.

Timofey decides to gift Alex a designer so that he can change his tree as he wants. Timofey knows that Alex is also lazy (a disaster, not a human being), so at the beginning of every day, he can perform no more than one operation of the following kind:

• Choose vertices $u$, $v_1$, and $v_2$ such that there is an edge between $u$ and $v_1$ and no edge between $u$ and $v_2$. Then remove the edge between $u$ and $v_1$ and add an edge between $u$ and $v_2$. This operation cannot be performed if the graph is no longer a tree after it.

Somehow Timofey managed to find out all the $d_i$. After that, he had another brilliant idea — just in case, make an instruction manual for the set, one that Alex wouldn't be disappointed.

Timofey is not as lazy as Alex, but when he saw the integer $n$, he quickly lost the desire to develop the instruction and the original tree, so he assigned this task to you. It can be shown that a tree and a sequence of operations satisfying the described conditions always exist.

Here is an example of an operation where vertices were selected: $u$ — $6$, $v_1$ — $1$, $v_2$ — $4$.

树是无环的连通图。可以证明，任意一棵含 $n$ 个顶点的树恰好有 $n - 1$ 条边。

叶节点（leaf）是指树中度数恰好为 1 的顶点（即恰好只与一条边相连的顶点）。

树中两个顶点 $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$ 的值。随后他又萌生了一个绝妙的想法——干脆提前制作一份详尽的操作说明书，确保亚历克斯每天都不会失望。

季莫费虽不像亚历克斯那么懒，但当他看到输入的整数 $n$ 后，立刻就丧失了自行设计初始树和操作序列的动力，于是把这项任务交给了你。可以证明：满足上述所有条件的一棵初始树及对应的操作序列总是存在的。

这是一个操作示例：所选顶点为 $u = 6$、$v_1 = 1$、$v_2 = 4$。

The first line contains the integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

The first line of each test case contains two integers $n$ ($3 \leq n \leq 500$) and $q$ ($1 \leq q \leq 500$) — the number of nodes in the tree and the number of days, respectively.

The $i$th of the following $q$ lines contains the integer $d_i$ ($2 \leq d_i \leq n - 1$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$. The same is guaranteed for $q$.

It can be shown that a tree and a sequence of operations satisfying the described conditions always exist.

第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。

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

接下来的 $q$ 行中，第 $i$ 行包含一个整数 $d_i$（$2 \leq d_i \leq n - 1$）。

保证所有测试用例中 $n$ 的总和不超过 $500$；对 $q$ 同样保证该条件成立。

可以证明：满足上述条件的树及操作序列一定存在。

For each test case, first print an $n - 1$ string describing the edges of the tree. If you want the tree to have an edge between nodes $u$ and $v$, there must be a string $v$ $u$ or $u$ $v$ among these $n - 1$ lines.

In the next $q$ lines, print three integers each $u$ $v_1$ $v_2$ — a description of the operations. If Alex doesn't need to perform an operation the following day, print $-1$ $-1$ $-1$.

对于每个测试用例，首先输出一个长度为 $n - 1$ 的字符串序列，用于描述树的边。若希望树中存在节点 $u$ 与 $v$ 之间的边，则这 $n - 1$ 行中必须包含形如 $v$ $u$ 或 $u$ $v$ 的字符串。

接下来的 $q$ 行中，每行输出三个整数 $u$ $v_1$ $v_2$ —— 描述一次操作。若 Alex 次日无需执行任何操作，则输出 $-1$ $-1$ $-1$。