分数: 600 点
问题陈述
给你一个字符串 S 由小写英文字母组成。
Alice 和 Bob 使用该字符串玩以下游戏。
- 准备一个空字符串 T.
- 从 Alice 开始,他们轮流玩。
- 每回合,玩家选择一个小写英文字母并将所选字母连接到 T。在这里,玩家不能采取这样的行动: 连接后的 T 不是以下的子串 S.
无法先行动的玩家失败。
确定当两名玩家都发挥最佳状态时哪个玩家将获胜。
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1\le T\le 10^5
- T 是一个整数。
- S 是由小写英文字母组成的字符串,长度介于 1 和 2\times 10^5,包括在内。
- 的长度总和 S 所有测试用例最多 4\times 10^5.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出。
S
输出
按顺序输出测试用例的答案,以换行符分隔。
对于每个测试用例,输出 Alice 如果当两个玩家都发挥最佳状态时爱丽丝获胜,并且 Bob 如果鲍勃获胜。
样本输入 1
4 ooxo abrakadabra atcoderbeginnercontest baabca
示例输出 1
Bob Alice Alice Bob
考虑第一个测试用例。
例如,游戏进行如下。
- 爱丽丝选择
x. T=x. - 鲍勃选择
o. T=xo. - 无论Alice选择哪个小写英文字母并连接到末尾 T, T 不会是以下的子串 S,因此 Alice 无法移动。至此,鲍勃获胜。
在这个测试用例中,无论 Alice 如何玩,Bob 都可以获胜。因此,输出 Bob.