A16308 | 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$ .

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.

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$ .