Tournament Manipulation

A soccer tournament has $n$ teams. In the first round there are $n/2$ matches, and the winner of each match advances to the next round. The second round has $n/4$ matches, and this repeats until the final match between the last two teams. The winner of the final becomes the tournament champion.

Sunyoung owns a soccer team. It is not the strongest team in the world, but it is quite strong: it can surely beat at least half of the teams in the tournament. Moreover, for every team $t$ that Sunyoung's team cannot beat, there always exists a team $t'$ that beats $t$ while itself losing to Sunyoung's team.

You may arrange the bracket however you like: in each round you may pair up the teams that reached that round into matches in any way you want. The outcome of a match is already fixed by the head-to-head record of the two teams and cannot be changed, but you decide who plays whom. Arrange the bracket so that Sunyoung's team (team $1$) wins the tournament.

If several brackets let team $1$ win, output only the lexicographically smallest one. The ordering is defined in the Output section.

The input consists of several test cases; there are at most $20$ of them.

The first line of each test case contains the number of teams $n$ ($2 \le n \le 8$, and $n$ is a power of two). Teams are numbered from $1$ to $n$, and Sunyoung's team is team $1$.

The next $n$ lines each contain a binary string of length $n$. If the $k$-th character of the $j$-th line is 1, then team $j$ can beat team $k$; otherwise it is 0 (there are no draws). A team cannot play itself, so the $j$-th character of the $j$-th line is always 0. For distinct $j$ and $k$, the $k$-th character of the $j$-th line and the $j$-th character of the $k$-th line differ.

The input continues until end of file.

For each test case, print a bracket that makes Sunyoung's team win, using $n-1$ lines.

The first $n/2$ lines are the matches of the first round, the next $n/4$ lines are the matches of the second round, and so on, with the last single line being the final. The teams appearing in the matches of a round must be exactly the teams that reached that round (the winners of the previous round), and each team plays exactly once per round.

Each line contains two integers, meaning those two teams play each other in that match.

Because several winning brackets may exist, output only the lexicographically smallest one under the following rules.

• When printing a match on a line, write the smaller of the two team numbers first.
• Within the same round, sort the matches in ascending order by first number, then by second number.
• To compare two brackets, sort and print them by the rules above, then read the integers top to bottom and left to right into one sequence and compare the sequences lexicographically. The bracket with the smaller sequence is the answer.

Print the outputs of the test cases one after another, with no blank line or separator between them.