AT_nupc2024_j.Cops and Robbers on Namori

Alice 和 Bob 想要在图上玩“捉迷藏”游戏。

在图上的捉迷藏游戏中，Alice 和 Bob 轮流进行以下两种操作之一：

• 从当前所在的顶点移动到相邻的其他顶点。
• 停留在原地不动（即“跳过”操作）。

在 Alice 行动之后，如果 Alice 和 Bob 站在同一个顶点，则 Alice 可以捉住 Bob。

给定一个有 $N$ 个顶点和 $N$ 条边的简单无向连通图，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

Alice 和 Bob 一开始分别站在顶点 $a$ 和 $b$，游戏从 Alice 的回合开始。请判断 Alice 是否必然能够在有限回合内捉住 Bob。注意，Alice 和 Bob 都能够实时得知彼此的位置，Alice 会尽可能快地捉住 Bob，而 Bob 会尽可能不被捉住。

输入按照以下格式从标准输入中给出。

$N \ a \ b\ u_1\ v_1\ u_2\ v_2\ \cdots\ u_N\ v_N$

如果 Alice 必然能够在有限回合内捉住 Bob，请输出 Alice，否则输出 Bob。

样例解释 1

例如，可能有以下的行动顺序：

• Alice 选择跳过。
• Bob 移动到顶点 $5$。
• Alice 移动到顶点 $6$ 并捉住 Bob。

这只是一种可能的过程，但对于给定的样例输入，可以证明 Alice 必然能够在有限回合内捉住 Bob。

数据范围

• $3 \leq N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• $1 \leq a, b \leq N$
• $a \neq b$
• 给定的图是简单图，即没有自环也没有重边。
• 给定的图是连通图。
• 所有输入都是整数。

由 ChatGPT 5 翻译