407720: GYM102881 I Ehab The Baby Learned Graphs

After learning to walk, Ehab the baby started learning graph theory. He never found the definition of the $$$xor$$$ of 2 graphs, so he decided that the $$$xor$$$ of 2 undirected graphs having the same number of vertices is defined as follows: the resulting graph has the same number of vertices and an edge exists in it if and only if it exists in exactly one of the two input graphs.

Now, Ehab made a new graph out of.. Well.. His cubes. The graph is undirected and connected, and it has $$$n$$$ vertices and $$$m$$$ edges. Ehab asked his "babysitter" Laggy to find at most $$$n+m$$$ trees consisting of $$$n$$$ nodes such that:

• His graph is the $$$xor$$$ of them. The $$$xor$$$ of one tree is itself. The $$$xor$$$ of $$$t>1$$$ trees is (the $$$xor$$$ of the first $$$t-1$$$ trees) $$$xor$$$ (the last tree).
• If you take the diameter of each tree and take the maximum of them, the result should be as small as possible. The diameter of a tree is the length of its longest path.

Laggy, of course, didn't solve it, so it's your turn. Can you solve it?

The first line contains a single integer integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of vertices in the graph.

The next $$$n$$$ lines contain $$$n$$$ integers each. If the $$$j_{th}$$$ number in the $$$i_{th}$$$ line is 1, then vertices $$$i$$$ and $$$j$$$ are connected by an edge. If it's 0, then they're not.

It's guaranteed that the graph is connected and doesn't have self-loops.

If it's impossible to solve the problem for this case, print one line containing "-1". Otherwise:

On the first line, print the number of trees $$$t$$$ you wish to use. It should be at most $$$n+m$$$.

On the next $$$t$$$ output blocks, you should print the trees. Each block consists of $$$n-1$$$ lines containing 2 integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$) which mean that there's an edge between nodes $$$u$$$ and $$$v$$$ in this tree. Each block must describe a tree.

If there are multiple solutions, print any of them. You can print the edges of a tree in any order.

4
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0

4
3 1
3 2
1 4
3 2
3 4
4 1
2 3
2 4
3 1
2 1
2 4
1 3

3
0 1 1
1 0 1
1 1 0

-1

3
0 1 1
1 0 0
1 0 0

1
1 2
1 3