Description

有 $k$ 个人在一个连通无向简单图上玩游戏，该图有 $n$（$n \ge 2$）个顶点（编号为 $0$ 到 $n-1$）和 $m$ 条边。这 $k$ 个人，编号为 $0$ 到 $k-1$，被分成两组，游戏规则如下：

• 他们轮流进行操作。也就是说，第 $0$ 个人进行第 $1$ 步操作，第 $1$ 个人进行第 $2$ 步操作，依此类推，第 $(i \bmod k)$ 个人进行第 $(i+1)$ 步操作。
• 每当轮到某个人时，当前玩家必须从当前图中选择一条边，并将其移除。如果移除该边后图不再连通，则该玩家所属的小组输掉比赛（并且对方小组获胜），游戏立即结束。

给你游戏开始时的初始图信息，若所有人都以最优策略为本组争取胜利，问最终哪一组会赢？

注意，简单图指的是没有自环和重边的无向图。

Input Format

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

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

第二行包含一个长度为 $k$ 的字符串 $s_0s_1\dots s_{k-1}$（$s_i \in \{\text{`1'}, \text{`2'}\}$）。$s_i = \text{`1' }$ 表示编号 $i$ 号的人属于第 1 组，$s_i = \text{`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$。

Output Format

对于每组测试数据，输出一行一个整数。如果第 1 组获胜，输出 1；如果第 2 组获胜，输出 2。

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

2
1
2

Hint

由 ChatGPT 5 翻译