← 返回题目列表

AtCoder · nupc2024_j

J. 纳莫里的警察与强盗

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

配点 : 100 点

問題文

Alice 和 Bob 正在尝试在图表上与 Keidro 一起玩。

图表上的 Keidro 在回合系统中交替执行以下操作。

  • 从当前顶点移动到相邻顶点。
  • 通过。 (保持在你所在的顶部。)

如果 Alice 和 Bob 在 Alice 执行一个动作后立即位于同一顶点,则 Alice 可以抓住 Bob。

爱丽丝和鲍勃玩耍 我们给出了一个简单的无向连通图 N 頂点 N 辺。 i 第一条边是顶点 u_i 和顶点 v_i 是平局。

Alice 和 Bob 各是一个顶点 从爱丽丝在 a, b 中的回合开始。 判断Alice是否一定能在有限的回合内抓住Bob。 然而,Alice和Bob都知道对方的位置,Alice尽可能地捕获Bob,而Bob则尽可能避免被Alice捕获。

制約

  • 3 \le N \le 2\times 10^5
  • 1 \le u_i,v_i \le N
  • 1 \le a,b \le N
  • a \neq b
  • 给出的图表很简单。也就是说,不存在自环或多重边。
  • 给定的图形已连接。
  • 所有输入均为整数。

入力

输入是按以下格式从标准输入给出的。 请按降序输出

N a b
u_1 v_1
u_2 v_2
\vdots
u_N v_N

出力

当 Alice 总能在有限的回合内抓住 Bob 时Alice,当它不是Bob。


入力例 1

6 2 6
1 2
1 4
2 3
2 5
3 4
5 6

出力例 1

Alice

例如,以下进展是可能的。

  • 爱丽丝通过了。
  • 鲍勃是顶级 转至 5 。
  • 爱丽丝是最上面的 前往 6 并抓住鲍勃。

这个进展只是一个例子,但是这个输入示例证明了 Alice 总能在有限的回合内抓住 Bob。


入力例 2

4 1 2
1 2
1 4
2 3
3 4

出力例 2

Alice

入力例 3

6 6 1
1 2
1 4
2 3
2 5
3 4
5 6

出力例 3

Bob