310852: CF1899F. Alex's whims

F. Alex's whimstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

Input

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.

Output

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

ExampleInput

3
3 3
2
2
2
5 6
4
2
3
4
3
2
4 9
2
3
3
2
2
2
3
2
2

Output

1 2
2 3
-1 -1 -1
-1 -1 -1
-1 -1 -1
1 2
2 3
3 4
4 5
-1 -1 -1
4 3 2
5 4 3
4 2 5
4 5 2
5 3 4
1 2
2 3
3 4
4 3 2
4 2 3
-1 -1 -1
4 3 2
-1 -1 -1
-1 -1 -1
4 2 3
4 3 2
-1 -1 -1

题目大意：
给定一个由n个顶点组成的树（一个无环的连通图），任意一棵n个顶点的树恰好有n-1条边。叶节点是树中仅有一条边与之相连的顶点。树中两个顶点u和v之间的距离是到达顶点v必须经过的最少边数。每天，Alex会选择一个整数d_i，如果在这一天树中没有两个叶节点之间的距离正好是d_i，Alex会感到失望。每天，Timofey可以进行一次操作，选择顶点u、v1和v2，使得u和v1之间有边而u和v2之间无边，然后移除u和v1之间的边并添加u和v2之间的边，这个操作不能使图不再是树。任务是找到一棵树和一系列操作，使得Alex在q天内不会感到失望。

输入数据格式：
第一行包含一个整数t（1≤t≤100），表示测试用例的数量。
每个测试用例的第一行包含两个整数n（3≤n≤500）和q（1≤q≤500），分别表示树中节点的数量和天数。
接下来q行，每行包含一个整数d_i（2≤d_i≤n-1）。
保证所有测试用例的n之和不超过500，q之和也不超过500。

输出数据格式：
对于每个测试用例，首先输出n-1行描述树的边。如果希望树在节点u和v之间有一条边，则这n-1行中必须包含字符串“v u”或“u v”。
接下来输出q行，每行输出三个整数u v1 v2，描述操作。如果Alex在接下来的那一天不需要执行操作，输出“-1 -1 -1”。题目大意： 给定一个由n个顶点组成的树（一个无环的连通图），任意一棵n个顶点的树恰好有n-1条边。叶节点是树中仅有一条边与之相连的顶点。树中两个顶点u和v之间的距离是到达顶点v必须经过的最少边数。每天，Alex会选择一个整数d_i，如果在这一天树中没有两个叶节点之间的距离正好是d_i，Alex会感到失望。每天，Timofey可以进行一次操作，选择顶点u、v1和v2，使得u和v1之间有边而u和v2之间无边，然后移除u和v1之间的边并添加u和v2之间的边，这个操作不能使图不再是树。任务是找到一棵树和一系列操作，使得Alex在q天内不会感到失望。 输入数据格式： 第一行包含一个整数t（1≤t≤100），表示测试用例的数量。 每个测试用例的第一行包含两个整数n（3≤n≤500）和q（1≤q≤500），分别表示树中节点的数量和天数。 接下来q行，每行包含一个整数d_i（2≤d_i≤n-1）。 保证所有测试用例的n之和不超过500，q之和也不超过500。 输出数据格式： 对于每个测试用例，首先输出n-1行描述树的边。如果希望树在节点u和v之间有一条边，则这n-1行中必须包含字符串“v u”或“u v”。 接下来输出q行，每行输出三个整数u v1 v2，描述操作。如果Alex在接下来的那一天不需要执行操作，输出“-1 -1 -1”。