Colorgraph

Lora is playing an online puzzle game. She receives an undirected graph with $N$ vertices, numbered from 1 to $N$. Every pair of distinct vertices is joined by an edge, colored either blue or red.

The graph is red-connected if any vertex can reach any other vertex using only red edges. Similarly, it is blue-connected if any vertex can reach any other vertex using only blue edges.

The state of the graph is a pair $(A, B)$, where:

• $A=1$ if the graph is red-connected, and $A=0$ if it is not
• $B=1$ if the graph is blue-connected, and $B=0$ if it is not

For example, state $(1, 0)$ describes a graph that is red-connected but not blue-connected.

With one click on an edge, Lora can change its color, from blue to red or from red to blue. Given an initial graph and a desired final state, the goal is to reach a graph in that final state with the minimum number of clicks. Write a program colorgraph that finds this minimum number of clicks.

The first line contains the positive integer $N$, the number of vertices. Each of the next $N$ lines contains $N$ space-separated numbers describing the edge colors. Let $G_{ij}$ be the $j$-th number on the $i$-th line. If $G_{ij}=0$, the edge between $i$ and $j$ is red. If $G_{ij}=1$, it is blue. It is guaranteed that $G_{ij}=G_{ji}$. For $i=j$, the value of $G_{ij}$ does not matter because the graph has no loops.

The last line contains two space-separated numbers $A$ and $B$, the desired final state.

If the graph cannot be transformed into the desired state, print -1 on a single line.

Otherwise, print the integer $K$, the minimum number of clicks, on the first line. Each of the next $K$ lines contains a pair of numbers, the two endpoints of an edge that Lora should click. If there is more than one solution, print any of them. The order of the edges and the order of the two endpoints in each pair do not matter.

Time limit: 2000 ms. Memory limit: 512 MB.

$3 \le N \le 250$

Red edges are drawn with solid lines, and blue edges with dotted lines.

In the first sample, the initial graph is in state (1, 0):

After changing edges 1-3 and 4-3, the graph reaches the desired state (0, 1):

In the second sample, no graph with 3 vertices has state (1, 1).

In the third sample, the graph already has the desired final state.