T2208D1. Tree Orientation (Easy Version)

constructive algorithms, dfs and similar, dsu, graphs, greedy, matrix, trees, https://codeforces.com/problemset/problem/2208/D1

This is the easy version of the problem. The difference between the versions is that in this version, the constraint on 𝑛 is lower. You can hack only if you solved all versions of this problem.

You once had an undirected tree with 𝑛 nodes. To make the tree look more interesting, you decided to assign an arbitary direction to each of the 𝑛−1 edges.

As time goes by, you forgot the structure of your tree. However, you found a note which recorded after the direction of the edges have been assigned, whether 𝑢 can reach 𝑣∗ for all ordered pairs of (𝑢,𝑣) which satisfies 1≤𝑢,𝑣≤𝑛.

You want to find out the structure of the tree and the direction of the edges from the information given by the note. Determine if there is possible solution and construct one. If there are multiple solutions, you only need to find one of them.

∗For a directed graph, we say that 𝑥 can reach 𝑦 if and only if there exists a sequence of nodes 𝑢1,𝑢2,…,𝑢𝑘 such that 𝑢1=𝑥,𝑢𝑘=𝑦 and for all 𝑖 from 2 to 𝑘, the directed edge 𝑢𝑖−1→𝑢𝑖 exists. In particular, a node can always reach itself.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤10^4). The description of the test cases follows.

The first line of each test cases contain an integer 𝑛 (2≤𝑛≤500) denoting the number of nodes your tree have.

The following 𝑛 lines contain a string 𝑠𝑖. 𝑠𝑖 is of length 𝑛 and consists only of 0 and 1. The 𝑗-th character of 𝑠𝑖 is 1 if and only if 𝑖 can reach 𝑗 after the edges are directed.

It is guaranteed that the sum of 𝑛^3 over all test cases does not exceed 500^3.

Output

For each testcase, output 𝚈𝚎𝚜 if a solution exists, otherwise print 𝙽𝚘. If the answer is 𝚈𝚎𝚜, on the following lines output a description of the edges constructed.

Output 𝑛−1 lines denoting the directed edges. Each line should contain two integers 𝑥 and 𝑦, denoting that after the edges are directed, the directed edge 𝑥→𝑦 exists. If there are multiple solutions, print any of them.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example

input

output

Yes
2 3
2 4
3 1
No
No
Yes
2 3
4 1
4 2
No
No
Yes
2 1
3 1
3 5
4 3
No
No
Yes
1 2
1 3
4 2
Yes
2 3
3 1

Note

For the first test case, nodes 1 and 4 can only reach themselves, node 2 can reach every node, node 3 can only reach node 1 and 3. The constructed edges satisfy this constraint.

For the second test case, it can be proven that no possible solution exists.

【尹显齐物院】对于这种矩阵，我们先判断它能不能形成一个有效的结构，即满足自洽性。我们用 $a r r (i, j)$ 表示第 $i$ 行第 $j$ 列的位置，首先，必须有 $a r r (i, i) = 1$ ，具体原因无需多说；接着，如果 $a r r (i, k) = a r r (k, j) = 1$ ，那么 $a r r (i, j) = 1$ 必须成立，不然就不自洽了。

判断完自洽性以后，我们就可以开始连线了。我们的目标是找到直接连接两个点的所有边，容易得到，对于两个点 $i, j$ ，它们要相连，必须有 $a r r (i, j) = 1$ 成立，并且由于两点之间只能有唯一的一条路径（假设从 $i$ 到 $j$ 有 $d$ 条不重合的路径，总共包含 $m$ 个节点，则连线数量为

\frac{2 (m - 2) + 2 d}{2} = m - 2 + d

从这个图形不断新增点与连线，就可形成所有 $n$ 个点所构成的图形，由于每添加一个点，必须添加一条边（否则无法连通），所有最终的图形会有 $n - 2 + d$ 条边。明显只有当 $d = 1$ 时满足题目条件。）所以不可能存在 $k$ 使得 $a r r (i, k) = a r r (k, j) = 1$ 成立。这就是我们判断出两个点是否有边连接的方式。

连好所有边之后，我们就要检查它是否是一个树了，首先，边数一定是 $n - 1$ ，其次我们要判断 $n$ 个点是否都连通，我们只要把有向边改成无向边，再用bfs/dfs从某个节点遍历一次，看能不能遍历到所有点即可。

主要难点：代码量大。

python

for _ in range(int(input())):
    n = int(input())
    arr = []
    for _ in range(n):
        s = input()
        row = [int(ch) for ch in s]
        arr.append(row)
    found = 0
    # 判断是否是自洽的矩阵
    for i in range(n):
        if arr[i][i] != 1:
            found = 1
            break
    if found:
        print("No")
        continue
    for i in range(n):
        for k in range(n):
            if arr[i][k] == 0:
                continue
            for j in range(n):
                if arr[k][j] and arr[i][j] != 1:
                    found = 1
                    break
            if found:
                break
        if found:
            break
    if found:
        print("No")
        continue
    # 连边
    edges = []
    for i in range(n):
        for j in range(n):
            if i == j or arr[i][j] == 0:
                continue
            is_direct = 1
            for k in range(n):
                if k != i and k != j and arr[i][k] and arr[k][j]:
                    is_direct = 0
                    break 
            if is_direct:
                edges.append((i,j))
    if len(edges) != n-1:
        print("No")
        continue
    # 建无向边图
    graph = [[] for _ in range(n)]
    for u,v in edges:
        graph[u].append(v)
        graph[v].append(u)
    visited = [0] * n
    stack = [0]
    visited[0] = 1
    count = 1
    while stack:
        u = stack.pop()
        for v in graph[u]:
            if not visited[v]:
                visited[v] = 1
                count += 1
                stack.append(v)
    if count == n:
        print("Yes")
        for u,v in edges:
            print(u+1,v+1)
    else:
        print("No")

T2208D1. Tree Orientation (Easy Version) ​

T2208D1. Tree Orientation (Easy Version)