题目描述

Lora 正在玩一个在线益智游戏。她得到了一张有 $N$ 个顶点的无向图，顶点编号为 $1$ 到 $N$。图满足：任意两个不同顶点之间都有一条边，这条边要么是蓝色，要么是红色。

如果从任意一个顶点都能只沿着红边到达任意另一个顶点，我们称这张图是 red-connected（红连通）的。类似地，如果从任意一个顶点都能只沿着蓝边到达任意另一个顶点，则称它是 blue-connected（蓝连通）的。

我们把图的状态定义为一个二元组 $(A,B)$：

• 若图是红连通的，则 $A=1$，否则 $A=0$；
• 若图是蓝连通的，则 $B=1$，否则 $B=0$。

例如，状态 $(1,0)$ 表示图是红连通的，但不是蓝连通的。

Lora 可以通过一次点击某条边，把这条边的颜色反转（蓝变红或红变蓝）。

现在给定一张初始图和一个目标状态，请你帮助 Lora 计算：至少需要点击多少次，才能把初始图变成一个处于目标状态的图。

如果有解，你还需要给出任意一种最优方案。

输入格式

第一行输入一个正整数 $N$，表示图中顶点个数。

接下来输入 $N$ 行，每行有 $N$ 个用空格分隔的数字，表示边的颜色。记第 $i$ 行第 $j$ 个数为 $G_{ij}$：

• 若 $G_{ij}=0$，则顶点 $i$ 与 $j$ 之间的边是红色；
• 若 $G_{ij}=1$，则顶点 $i$ 与 $j$ 之间的边是蓝色。

保证 $G_{ij}=G_{ji}$。当 $i=j$ 时，$G_{ij}$ 的值无关紧要，因为图中没有自环。

最后一行输入两个用空格分隔的数 $A$ 和 $B$，表示目标状态。

输出格式

如果无法把初始图变换成目标状态，则输出一行 -1。

否则：

• 第一行输出一个整数 $K$，表示最少需要点击的次数；
• 接下来 $K$ 行，每行输出一对整数，表示需要点击的那条边的两个端点。

若存在多种方案，输出任意一种即可。边的输出顺序、以及一条边两个端点的先后顺序都不作要求。

数据范围

• $3 \le N \le 250$

子任务与评分

测试按两两成组的方式计分。想拿到某一组的分数，你的程序必须在该组中的两个测试点上都正确。

子任务	测试占比	额外限制
1	$15\%$	$N \le 7$
2	$35\%$	目标状态是 $(1,1)$
3	$50\%$	目标状态不是 $(1,1)$

样例 1

输入

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

输出

2
1 3
4 3

样例 2

输入

3
0 1 1
1 0 0
1 0 0
1 1

输出

-1

样例 3

输入

3
0 1 1
1 0 0
1 0 0
0 1

输出

0

样例解释

红边用实线表示，蓝边用虚线表示。

在第一个样例中，初始图的状态是 $(1,0)$。

将边 $1-3$ 和 $4-3$ 的颜色翻转之后，图就变成了目标状态 $(0,1)$，如下所示：

第二个样例说明：当 $N=3$ 时，不存在状态为 $(1,1)$ 的图。

第三个样例说明：初始图本身就已经处于目标状态。