Alex's whims (Codeforces 1899F)
Tags: Greedy, shortest paths

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


Sample Inputs:
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

Sample Outputs:
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

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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])