Omkar and Heavenly Tree (Codeforces 1583B)
Tags: Others, trees

Lord Omkar would like to have a tree with $$$n$$$ nodes ($$$3 \le n \le 10^5$$$) and has asked his disciples to construct the tree. However, Lord Omkar has created $$$m$$$ ($$$\mathbf{1 \le m < n}$$$) restrictions to ensure that the tree will be as heavenly as possible. A tree with $$$n$$$ nodes is an connected undirected graph with $$$n$$$ nodes and $$$n-1$$$ edges. Note that for any two nodes, there is exactly one simple path between them, where a simple path is a path between two nodes that does not contain any node more than once.Here is an example of a tree:   A restriction consists of $$$3$$$ pairwise distinct integers, $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \le a,b,c \le n$$$). It signifies that node $$$b$$$ cannot lie on the simple path between node $$$a$$$ and node $$$c$$$. Can you help Lord Omkar and become his most trusted disciple? You will need to find heavenly trees for multiple sets of restrictions. It can be shown that a heavenly tree will always exist for any set of restrictions under the given constraints.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). Description of the test cases follows.The first line of each test case contains two integers, $$$n$$$ and $$$m$$$ ($$$3 \leq n \leq 10^5$$$, $$$\mathbf{1 \leq m < n}$$$), representing the size of the tree and the number of restrictions.The $$$i$$$-th of the next $$$m$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ ($$$1 \le a_i, b_i, c_i \le n$$$, $$$a$$$, $$$b$$$, $$$c$$$ are distinct), signifying that node $$$b_i$$$ cannot lie on the simple path between nodes $$$a_i$$$ and $$$c_i$$$. It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$10^5$$$.

Output: For each test case, output $$$n-1$$$ lines representing the $$$n-1$$$ edges in the tree. On each line, output two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) signifying that there is an edge between nodes $$$u$$$ and $$$v$$$. Given edges have to form a tree that satisfies Omkar's restrictions.

Note: The output of the first sample case corresponds to the following tree:    For the first restriction, the simple path between $$$1$$$ and $$$3$$$ is $$$1, 3$$$, which doesn't contain $$$2$$$. The simple path between $$$3$$$ and $$$5$$$ is $$$3, 5$$$, which doesn't contain $$$4$$$. The simple path between $$$5$$$ and $$$7$$$ is $$$5, 3, 1, 2, 7$$$, which doesn't contain $$$6$$$. The simple path between $$$6$$$ and $$$4$$$ is $$$6, 7, 2, 1, 3, 4$$$, which doesn't contain $$$5$$$. Thus, this tree meets all of the restrictions.The output of the second sample case corresponds to the following tree:   

Sample Inputs:
2
7 4
1 2 3
3 4 5
5 6 7
6 5 4
5 3
1 2 3
2 3 4
3 4 5

Sample Outputs:
1 2
1 3
3 5
3 4
2 7
7 6
5 1
1 3
3 2
2 4

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
import itertools
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    (n, m) = map(int, readline().split())
    cnt = [0 for _ in range(n)]
    for i in range(m):
        (a, b, c) = map(int, readline().split())
        b -= 1
        cnt[b] += 1
    for i in range(n):
        if cnt[i] == 0:
            for j in range(n):
                if j != i:
                    print(i + 1, j + 1)
            return

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log, log2, pi, ceil, prod
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from heapq import *
from collections import deque, Counter as ctr
inp = lambda : int(stdin.readline())
inpf = lambda : float(stdin.readline())
inps = lambda : stdin.readline().strip()
seq = lambda : list(map(int, stdin.readline().strip().split()))
seqc = lambda : list(stdin.readline().strip())
mul = lambda : map(int, stdin.readline().strip().split())
mulf = lambda : map(float, stdin.readline().strip().split())
muls = lambda : stdin.readline().strip().split()
jn = lambda x, l: x.join(map(str, l))
ceildiv = lambda x, d: -(x // -d)
flush = lambda : stdout.flush()
fastprint = lambda x: stdout.write(str(x))
mod = 998244353

def main():
    [n, m] = seq()
    ds = set()
    for _ in range(m):
        [a, b, c] = seq()
        ds.add(b)
    for x in range(1, n + 1):
        if x not in ds:
            for i in range(1, n + 1):
                if i != x:
                    print(i, x)
            return
MULT = True
rg = inp() if MULT else 1
for i in range(rg):
    ret = main()
    if ret is not None:
        if isinstance(ret, tuple) or isinstance(ret, list):
            print(*ret)
        else:
            print(ret)

Solution (Python):
number_of_tests = int(input())
for _ in range(number_of_tests):
    (n, m) = [int(x) for x in input().split(' ')]
    number_of_restrictions = {}
    for i in range(n):
        number_of_restrictions[i + 1] = 0
    for i in range(m):
        (a, b, c) = [int(x) for x in input().split(' ')]
        number_of_restrictions[b] += 1
    for i in number_of_restrictions:
        if number_of_restrictions[i] == 0:
            if i == 1:
                for j in range(2, n + 1):
                    print(f'1 {j}')
            else:
                for j in range(1, i):
                    print(f'{i} {j}')
                for j in range(i + 1, n + 1):
                    print(f'{i} {j}')
            break