配点 : 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