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$$$.
def solve():
    (n, numdays) = [int(x) for x in input().split()]
    for i in range(1, n):
        print(i, i + 1)
    attached = n - 1
    for i in range(numdays):
        distNeed = int(input())
        newAttach = n - distNeed
        if newAttach == attached:
            print(-1, -1, -1)
        else:
            print(n, attached, n - distNeed)
            attached = newAttach
t = int(input())
for i in range(t):
    solve()
from sys import stdin
INF = float('inf')
input = lambda : stdin.readline().rstrip('\n')
t = 1
t = int(input())

def solve():
    (n, q) = [int(i) for i in input().split()]
    d = []
    for i in range(q):
        d.append(int(input()))
    for i in range(n - 2):
        print(i + 1, i + 2)
    print(n - 2, n)
    curr_d = 2
    curr_node = n - 2
    for i in range(q):
        if curr_d == d[i]:
            print(-1, -1, -1)
        else:
            need_node = n - 1 - (d[i] - 1)
            print(n, curr_node, need_node)
            curr_node = need_node
            curr_d = d[i]
    return
for _ in range(t):
    solve()
for _ in [0] * int(input()):
    (n, q) = map(int, input().split())
    for i in range(2, n + 1):
        print(i, i - 1)
    l = n - 1
    for j in range(q):
        b = int(input())
        exec(['print(n,l,l:=b)', 'print(-1,-1,-1)'][l == b])