AT_2_ttpc2024_2_n.Adjacent Game

给定一棵包含 $N$ 个顶点的树。树中顶点编号为 $1$ 到 $N$，第 $i$ 条边 （$1 \leq i \leq N-1$）连接顶点 $u_i$ 和 $v_i$。

Alice 和 Bob 进行一个轮流打标记的游戏。初始时，所有顶点都没有标记。

游戏规则如下：首先，Alice 可以任意选择一个顶点打上她的标记。然后，从 Bob 开始，双方轮流进行操作。无法进行合法操作的一方输掉游戏，反之，另一方获胜。

操作步骤为：

• 选择一个未被标记的顶点 $v$。
• 顶点 $v$ 与一个有对方标记的顶点 $u$ 相邻。
• 在顶点 $v$ 上打上自己的标记。

假设双方都以最优策略行动，问谁将获胜。

输入以如下形式提供：

$N$
$u_1$ $v_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$

如果 Alice 胜出，输出 Alice；如果 Bob 胜出，输出 Bob。

• 所有输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• 输入的图结构始终为一棵树。

示例解读

考虑这样一个情形：

1. 开始时，Alice 在顶点 $1$ 上标记。
2. 接着，Bob 在顶点 $2$ 上标记（顶点 $1$ 上有 Alice 的标记且顶点 $2$ 与顶点 $1$ 相连）。
3. Alice 在顶点 $3$ 上标记（顶点 $2$ 上有 Bob 的标记且顶点 $3$ 与顶点 $2$ 相连）。
4. Bob 在顶点 $4$ 上标记（顶点 $3$ 上有 Alice 的标记且顶点 $4$ 与顶点 $3$ 相连）。
5. Alice 在顶点 $5$ 上标记（顶点 $2$ 上有 Bob 的标记且顶点 $5$ 与顶点 $2$ 相连）。
6. Bob 无法进行任何操作，因此 Alice 胜出。

在这个示例中，很明显 Alice 有取胜的策略，因此答案为 Alice。

本翻译由 AI 自动生成