AT_abc427_d [ABC427D] The Simple Game

有一个有向图，包含 $N$ 个顶点和 $M$ 条边。顶点从 $1$ 到 $N$ 编号，第 $i$ 条边是从顶点 $U_i$ 指向顶点 $V_i$ 的有向边。保证每个顶点的出度至少为 $1$。 此外，每个顶点上写有一个字符，第 $i$ 个顶点写有字符 $S_i$。其中 $S_i$ 指第 $i$ 个字符，$S$ 是一个长度为 $N$ 的字符串。 Alice 和 Bob 在图上用一个棋子玩如下游戏： - 棋子最初放在顶点 $1$ 上。Alice 先手，Bob 后手，两人交替进行以下操作各 $K$ 次： - 设当前棋子在顶点 $u$。选择一个存在从 $u$ 到 $v$ 的有向边的顶点 $v$，并将棋子移动到 $v$ 上。 - 经过 $2K$ 步后，设棋子最终停在顶点 $v$。 - 若 $S_v=$ `A`，则 Alice 获胜； - 若 $S_v=$ `B`，则 Bob 获胜。 如果双方均采取最优策略，问谁会获胜。 输入包含 $T$ 组测试数据。请对每组数据分别作答。

输入从标准输入读取，格式如下： > $T$ $\text{case}_1$ $\text{case}_2$ $\ldots$ $\text{case}_T$ 其中 $\text{case}_i$ 表示第 $i$ 组测试数据，格式如下： > $N$ $M$ $K$ $S$ > $U_1$ $V_1$ > $U_2$ $V_2$ > $\vdots$ > $U_M$ $V_M$

输出 $T$ 行，第 $i$ 行输出当双方均采取最优策略时，第 $i$ 组测试数据的胜者。如果 Alice 获胜，则输出 `Alice`；如果 Bob 获胜，则输出 `Bob`。

### 样例解释 1 以下以第一组测试数据举例说明游戏过程。此过程不一定是最优策略，仅为示例。 - 初始时，棋子在顶点 $1$。 - Alice 将棋子移动到顶点 $2$。 - Bob 将棋子移动到顶点 $3$。 - Alice 再次将棋子移动到顶点 $3$。 - Bob 将棋子移动回到顶点 $1$。 此时有 $S_1=$ `A`，所以 Alice 获胜。 ### 数据范围 - $1 \leq T$ - $2 \leq N, M \leq 2 \times 10^5$ - $1 \leq K \leq 10$ - $S$ 是长度为 $N$ 仅包含 `A` 和 `B` 的字符串 - $1 \leq U_i, V_i \leq N$ - 若 $i \neq j$，则 $(U_i, V_i) \neq (U_j, V_j)$ - 每个顶点出度至少为 $1$ - 单组输入所有测试数据的 $N$ 之和不超过 $2\times 10^5$ - 单组输入所有测试数据的 $M$ 之和不超过 $2\times 10^5$ 由 ChatGPT 5 翻译