← 返回题目列表

AtCoder · abc427_d

G. 简单的游戏

中文机器翻译题面 查看原题

分数: 425 点

问题陈述

有一个有向图 N 顶点和 M 边缘。顶点编号从 1 to N,以及 i-th 边是从顶点开始的有向边 U_i 到顶点 V_i。这里,每个顶点的出度至少为 1.

另外,每个顶点上都写有一个字符,并且顶点上写的字符 i is S_i。在这里, S_i 指的是 i- 第一个字符 S.

Alice 和 Bob 使用一件棋子在此图上玩以下游戏:

  • 最初,该块放置在顶点 1,并且它们交替执行以下操作 各 K 次,Alice 首先,Bob 第二。

    • 让 u 是当前放置棋子的顶点。选择一个顶点 v 使得顶点有一条边 u 到顶点 v,并将棋子移动到顶点 v.
  • 让 v 是最终放置棋子的顶点。如果 S_v = A,爱丽丝获胜;如果 S_v = B,鲍勃获胜。

当双方都发挥最佳状态时找到游戏的获胜者。

在每个输入中,您都会得到 T 测试用例。解决它们中的每一个。

约束

  • 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
  • (U_i, V_i) \neq (U_j, V_j) if i \neq j .
  • 每个顶点的出度至少为 1.
  • 总和 N 单个输入中的所有测试用例最多 2 \times 10^5.
  • 总和 M 单个输入中的所有测试用例最多 2 \times 10^5.

输入

输入由标准输入按以下格式给出:

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- 第行应包含 Alice 如果当两个玩家都在最佳状态下玩时 Alice 获胜 i- 第一个测试用例,以及 Bob 如果鲍勃获胜。


示例输入 1

3
4 6 2
AABB
1 2
2 3
3 1
3 3
3 4
4 2
4 6 2
ABAB
1 2
2 3
3 1
3 3
3 4
4 2
5 8 3
ABABB
1 2
2 2
2 3
3 1
3 4
4 4
4 5
5 3

示例输出 1

Alice
Bob
Bob

我们将解释第一个测试用例中游戏如何进行的示例。在这里,两个玩家都不一定发挥最佳状态。

  • 最初,该块放置在顶点 1.
  • Alice 将棋子移动到顶点 2.
  • Bob 将棋子移动到顶点 3.
  • Alice 将棋子移动到顶点 3.
  • Bob 将棋子移动到顶点 1.

此时, S_1 = A,所以爱丽丝获胜。