컬러그래프

Lora는 온라인 퍼즐 게임을 하고 있다. 그녀는 정점이 $N$개인 무방향 그래프를 받는다. 정점에는 1부터 $N$까지 번호가 매겨져 있다. 서로 다른 두 정점 사이에는 반드시 간선이 하나 있고, 그 색은 파란색 또는 빨간색이다.

빨간 간선만 사용해서 어떤 정점에서든 다른 모든 정점에 도달할 수 있으면 그래프는 빨간색 연결이다. 마찬가지로 파란 간선만 사용해서 어떤 정점에서든 다른 모든 정점에 도달할 수 있으면 파란색 연결이다.

그래프의 상태는 다음 조건을 따르는 쌍 $(A, B)$이다.

• 빨간색 연결이면 $A=1$, 아니면 $A=0$
• 파란색 연결이면 $B=1$, 아니면 $B=0$

예를 들어 상태 $(1, 0)$은 빨간색 연결이지만 파란색 연결은 아닌 그래프를 나타낸다.

Lora는 간선 하나를 한 번 클릭하여 그 색을 파란색에서 빨간색으로, 또는 빨간색에서 파란색으로 바꿀 수 있다. 초기 그래프와 목표 최종 상태가 주어졌을 때, 최소 클릭 수로 최종 상태의 그래프를 만드는 것이 목표다. 이 최소 클릭 수를 구하는 프로그램 colorgraph를 작성하라.

첫 줄에는 정점의 개수를 나타내는 양의 정수 $N$이 주어진다. 이어지는 $N$개의 줄에는 간선의 색을 나타내는 $N$개의 수가 공백으로 구분되어 있다. $i$번째 줄의 $j$번째 수를 $G_{ij}$라고 하자. $G_{ij}=0$이면 정점 $i$와 $j$를 잇는 간선은 빨간색이고, $G_{ij}=1$이면 파란색이다. $G_{ij}=G_{ji}$가 보장된다. $i=j$인 경우 그래프에 자기 루프가 없으므로 $G_{ij}$의 값은 상관없다.

마지막 줄에는 목표 상태를 나타내는 두 수 $A$와 $B$가 공백으로 구분되어 주어진다.

그래프를 목표 상태로 바꿀 수 없으면 -1을 한 줄에 출력한다.

그렇지 않으면 첫 줄에 최소 클릭 수 $K$를 출력한다. 이어지는 $K$개의 줄에는 Lora가 클릭해야 하는 간선의 양 끝점을 나타내는 두 수를 한 쌍씩 출력한다. 해가 여러 개이면 아무거나 출력해도 된다. 간선의 순서와 각 쌍 안의 두 끝점 순서는 상관없다.

시간 제한: 2000 ms. 메모리 제한: 512 MB.

$3 \le N \le 250$

빨간 간선은 실선으로, 파란 간선은 점선으로 그려져 있다.

첫 번째 예제에서 초기 그래프의 상태는 (1, 0)이다.

간선 1-3과 4-3의 색을 바꾸면 그래프는 목표 상태인 (0, 1)이 된다.

두 번째 예제에서는 정점이 3개이고 상태가 (1, 1)인 그래프가 존재하지 않는다.

세 번째 예제에서는 그래프가 처음부터 목표 최종 상태이다.