Tree Recovery (Codeforces 1696F)
Tags: Others, dsu

Fishingprince loves trees. A tree is a connected undirected graph without cycles.Fishingprince has a tree of $$$n$$$ vertices. The vertices are numbered $$$1$$$ through $$$n$$$. Let $$$d(x,y)$$$ denote the shortest distance on the tree from vertex $$$x$$$ to vertex $$$y$$$, assuming that the length of each edge is $$$1$$$.However, the tree was lost in an accident. Fortunately, Fishingprince still remembers some information about the tree. More specifically, for every triple of integers $$$x,y,z$$$ ($$$1\le x<y\le n$$$, $$$1\le z\le n$$$) he remembers whether $$$d(x,z)=d(y,z)$$$ or not.Help him recover the structure of the tree, or report that no tree satisfying the constraints exists.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). Description of the test cases follows.The first line of each test case contains an integer $$$n$$$ ($$$2\le n\le 100$$$) — the number of vertices in the tree.Then $$$n-1$$$ lines follow. The $$$i$$$-th line of these $$$n-1$$$ lines contains $$$n-i$$$ strings of length $$$n$$$ consisting of 0 and 1. If the $$$k$$$-th character in the $$$j$$$-th string of the $$$i$$$-th line is 0, it means that $$$d(i,k)\ne d(i+j,k)$$$; if the $$$k$$$-th character in the $$$j$$$-th string of the $$$i$$$-th line is 1, it means that $$$d(i,k)=d(i+j,k)$$$.It is guaranteed that in one input file,  there are at most $$$2$$$ test cases that have $$$n>50$$$;  there are at most $$$5$$$ test cases that have $$$n>20$$$. 

Output: For each test case:  if no answer exists, output No;  otherwise, on the first line output Yes. Then output $$$n-1$$$ lines. Each line should contain two integers $$$x,y$$$ ($$$1\le x,y\le n$$$), denoting an edge between vertices $$$x$$$ and $$$y$$$ of the tree. If there are multiple solutions, print any. When printing Yes and No, you can print each letter in any case (upper or lower).


Sample Inputs:
5
2
00
2
10
3
001 000
000
3
001 010
000
5
00000 01001 00000 01100
00000 10000 00000
00000 11010
00000

Sample Outputs:
Yes
1 2
No
Yes
1 3
2 3
No
Yes
1 2
1 4
2 3
2 5

Solution (Python):
def query(i, j, k):
    return (s[i][j - i - 1][k] if i < j else s[j][i - j - 1][k]) == '1'

def check(g, root):
    if not all(g):
        return False
    depth = [None] * n
    depth[root] = 0
    parent = [None] * n
    stack = [root]
    while stack:
        i = stack.pop()
        for j in g[i]:
            if j != parent[i]:
                parent[j] = i
                depth[j] = depth[i] + 1
                stack.append(j)
    for i in range(n):
        for j in range(i + 1, n):
            if query(i, j, root) != (depth[i] == depth[j]):
                return False
    return True

def solve(k):
    g = [[] for _ in range(n)]
    g[0] = [k]
    g[k] = [0]
    visited = [False] * n
    visited[0] = visited[k] = True
    for stack in ([(0, k)], [(k, 0)]):
        while stack:
            (u, v) = stack.pop()
            for i in range(n):
                if not visited[i] and query(u, i, v):
                    visited[i] = True
                    g[v].append(i)
                    g[i].append(v)
                    stack.append((v, i))
    return g
for _ in range(int(input())):
    n = int(input())
    s = [input().split() for i in range(n - 1)]
    for k in range(1, n):
        g = solve(k)
        if all((check(g, root) for root in range(n))):
            print('Yes')
            for i in range(n):
                for j in g[i]:
                    if i < j:
                        print(i + 1, j + 1)
            break
    else:
        print('No')

Solution (Python):
def query(i, j, k):
    return (s[i][j - i - 1][k] if i < j else s[j][i - j - 1][k]) == '1'

def check(g, root):
    if not all(g):
        return False
    depth = [None] * n
    depth[root] = 0
    parent = [None] * n
    stack = [root]
    while stack:
        i = stack.pop()
        for j in g[i]:
            if j != parent[i]:
                parent[j] = i
                depth[j] = depth[i] + 1
                stack.append(j)
    for i in range(n):
        for j in range(i + 1, n):
            if query(i, j, root) != (depth[i] == depth[j]):
                return False
    return True

def solve(k):
    g = [[] for _ in range(n)]
    g[0] = [k]
    g[k] = [0]
    visited = [False] * n
    visited[0] = visited[k] = True
    for stack in ([(0, k)], [(k, 0)]):
        while stack:
            (u, v) = stack.pop()
            for i in range(n):
                if not visited[i] and query(u, i, v):
                    visited[i] = True
                    g[v].append(i)
                    g[i].append(v)
                    stack.append((v, i))
    return g
for _ in range(int(input())):
    n = int(input())
    s = [input().split() for i in range(n - 1)]
    for k in range(1, n):
        g = solve(k)
        if all((check(g, root) for root in range(n))):
            print('Yes')
            for i in range(n):
                for j in g[i]:
                    if i < j:
                        print(i + 1, j + 1)
            break
    else:
        print('No')

Solution (Python):
def query(i, j, k):
    return (s[i][j - i - 1][k] if i < j else s[j][i - j - 1][k]) == '1'

def check(g, root):
    if not all(g):
        return False
    depth = [None] * n
    depth[root] = 0
    parent = [None] * n
    stack = [root]
    while stack:
        i = stack.pop()
        for j in g[i]:
            if j != parent[i]:
                parent[j] = i
                depth[j] = depth[i] + 1
                stack.append(j)
    for i in range(n):
        for j in range(i + 1, n):
            if query(i, j, root) != (depth[i] == depth[j]):
                return False
    return True

def solve(k):
    g = [[] for _ in range(n)]
    g[0] = [k]
    g[k] = [0]
    visited = [False] * n
    visited[0] = visited[k] = True
    for stack in ([(0, k)], [(k, 0)]):
        while stack:
            (u, v) = stack.pop()
            for i in range(n):
                if not visited[i] and query(u, i, v):
                    visited[i] = True
                    g[v].append(i)
                    g[i].append(v)
                    stack.append((v, i))
    return g
for _ in range(int(input())):
    n = int(input())
    s = [input().split() for i in range(n - 1)]
    for k in range(1, n):
        g = solve(k)
        if all((check(g, root) for root in range(n))):
            print('Yes')
            for i in range(n):
                for j in g[i]:
                    if i < j:
                        print(i + 1, j + 1)
            break
    else:
        print('No')