分数: 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,所以爱丽丝获胜。