P14045 [SDCPC 2019] Game on a Graph

有 $k$ 个人在一个连通无向简单图上玩游戏，该图有 $n$（$n \ge 2$）个顶点（编号为 $0$ 到 $n-1$）和 $m$ 条边。这 $k$ 个人，编号为 $0$ 到 $k-1$，被分成两组，游戏规则如下： - 他们轮流进行操作。也就是说，第 $0$ 个人进行第 $1$ 步操作，第 $1$ 个人进行第 $2$ 步操作，依此类推，第 $(i \bmod k)$ 个人进行第 $(i+1)$ 步操作。 - 每当轮到某个人时，当前玩家必须从当前图中选择一条边，并将其移除。如果移除该边后图不再连通，则该玩家所属的小组输掉比赛（并且对方小组获胜），游戏立即结束。 给你游戏开始时的初始图信息，若所有人都以最优策略为本组争取胜利，问最终哪一组会赢？ 注意，简单图指的是没有自环和重边的无向图。

有多组测试数据。输入的第一行为整数 $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$。

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

由 ChatGPT 5 翻译