D1. Tree Orientation (Easy Version)
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

You once had an undirected tree with $$$n$$$ nodes. To make the tree look more interesting, you decided to assign an arbitary direction to each of the $$$n-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 $$$u$$$ can reach $$$v$$$$$$^{\text{∗}}$$$ for all ordered pairs of $$$(u,v)$$$ which satisfies $$$1\le u,v\le n$$$.

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.

$$$^{\text{∗}}$$$For a directed graph, we say that $$$x$$$ can reach $$$y$$$ if and only if there exists a sequence of nodes $$$u_1,u_2,\ldots,u_k$$$ such that $$$u_1=x,u_k=y$$$ and for all $$$i$$$ from $$$2$$$ to $$$k$$$, the directed edge $$$u_{i-1}\rightarrow u_i$$$ 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 $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test cases contain an integer $$$n$$$ ($$$2\le n\le 500$$$) denoting the number of nodes your tree have.

The following $$$n$$$ lines contain a string $$$s_i$$$. $$$s_i$$$ is of length $$$n$$$ and consists only of $$$0$$$ and $$$1$$$. The $$$j$$$-th character of $$$s_i$$$ is $$$1$$$ if and only if $$$i$$$ can reach $$$j$$$ after the edges are directed.

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

Output

For each testcase, output $$$\texttt{Yes}$$$ if a solution exists, otherwise print $$$\texttt{No}$$$. If the answer is $$$\texttt{Yes}$$$, on the following lines output a description of the edges constructed.

Output $$$n-1$$$ lines denoting the directed edges. Each line should contain two integers $$$x$$$ and $$$y$$$, denoting that after the edges are directed, the directed edge $$$x\rightarrow y$$$ 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
11
4
1000
1111
1010
0001
4
1111
0111
0010
0111
4
0011
0111
0011
0001
4
1000
0110
0010
1111
4
1000
0110
1010
1111
5
10000
01011
00111
00010
00001
5
10000
11000
10101
10111
00001
5
10000
01101
00100
01110
10001
4
1100
0100
0011
0001
4
1110
0100
0010
0101
3
100
111
101
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.