有 $k$ 个人在一个包含 $n$ ($n \ge 2$) 个顶点（编号从 $0$ 到 $n-1$）和 $m$ 条边的连通无向简单图上进行游戏。这 $k$ 个人编号从 $0$ 到 $k-1$，被分为两个阵营，游戏规则如下：

• 他们轮流进行操作。也就是说，0 号玩家进行第 1 次操作，1 号玩家进行第 2 次操作，以此类推，编号为 $(i \pmod k)$ 的玩家进行第 $(i+1)$ 次操作。
• 在一次操作中，当前玩家必须从当前图中选择一条边并将其删除。如果删除该边后图不再连通，则该玩家所属的阵营输掉比赛（对方阵营获胜），游戏立即结束。

给定游戏开始时的初始图，假设所有人都采取最优策略以使自己所属的阵营获胜，最终哪个阵营会获胜？

回想一下，简单图是指没有自环或重边的图。

输入格式

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

第一行包含一个整数 $k$ ($2 \le k \le 10^5$)，表示人数。

第二行包含一个长度为 $k$ 的字符串 $s_0s_1 \dots s_{k-1}$ ($s_i \in \{'1', '2'\}$)。$s_i = '1'$ 表示编号为 $i$ 的玩家属于第 1 阵营，$s_i = '2'$ 表示编号为 $i$ 的玩家属于第 2 阵营。

第三行包含两个整数 $n$ 和 $m$ ($2 \le n \le 10^5, n-1 \le m \le 10^5$)，表示初始图的顶点数和边数。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($0 \le u_i, v_i < n$)，表示初始图中连接顶点 $u_i$ 和 $v_i$ 的一条边。

保证： 初始图是一个连通无向简单图。 存在属于不同阵营的玩家。 * 所有测试数据中 $k$ 的总和、$n$ 的总和以及 $m$ 的总和均不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含一个整数。如果第 1 阵营获胜，输出 “1”（不含引号）；如果第 2 阵营获胜，输出 “2”（不含引号）。

样例

样例输入 1

3
5
11212
4 6
0 1
0 2
0 3
1 2
1 3
2 3
5
11121
5 7
0 2
1 3
2 4
0 3
1 2
3 2
4 1
3
121
4 3
0 1
0 2
1 3

样例输出 1

2
1
2