Professor Zhang 正在尝试解决 Karp 的 21 个 NP 完全问题之一：图着色问题。

首先，他生成了一个包含 $n$ 个顶点和 $m$ 条边的无向图。然后，他将所有顶点涂成黑色或白色。最后，他希望使用以下操作使顶点着色正确：选择两个相邻的顶点并交换它们的颜色。当且仅当没有两个相邻的顶点颜色相同时，顶点着色才是正确的。

Professor Zhang 想知道所需的最小操作次数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 500, 1 \le m \le \frac{n(n-1)}{2}$)，分别表示顶点数和边数。第二行包含一个长度为 $n$ 的二进制字符串。如果第 $i$ 个字符为 '0'，则第 $i$ 个顶点被涂成白色，否则涂成黑色。

接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le n, x_i \neq y_i$)，表示一条无向边。

测试数据最多有 200 组，且输入文件总大小不超过 1.5 MB。

输出格式

对于每组测试数据，首先输出一个整数 $s$，表示最小操作次数。接下来的 $s$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示第 $i$ 次操作。

如果不存在这样的解，则仅输出一行 “-1”。

样例

输入 1

3
4 4
0011
1 2
2 3
3 4
4 1
2 1
00
1 2
6 7
011001
1 4
1 5
4 2
5 2
5 3
2 6
6 3

输出 1

1
4 1
-1
2
2 4
3 5