← 返回题目列表

AtCoder · agc017_d

D. 树上的游戏

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

分数: 1100 点

问题陈述

有一棵树 N 顶点编号 1, 2, ..., N。 树的边缘表示为 (x_i, y_i).

在这棵树上,Alice 和 Bob 互相玩游戏。 从Alice开始,他们交替执行以下操作:

  • 选择一条现有边并将其从树中删除,将其断开为两个独立的连接组件。然后,删除不包含Vertex的组件 1.

当玩家无法执行该操作时,他/她就输掉了游戏。 假设双方都发挥最佳状态,确定游戏的获胜者。

约束

  • 2 \leq N \leq 100000
  • 1 \leq x_i, y_i \leq N
  • 给定的图是一棵树。

输入

输入由标准输入按以下格式给出:

N
x_1 y_1
x_2 y_2
:
x_{N-1} y_{N-1}

输出

打印 Alice 如果爱丽丝赢了;打印 Bob 如果鲍勃获胜。


示例输入 1

5
1 2
2 3
2 4
4 5

示例输出 1

Alice

如果 Alice 首先删除连接顶点的边 1 和 2,树成为仅包含 Vertex 的单顶点树 1。 由于不再有边,鲍勃无法执行该操作,爱丽丝获胜。


示例输入 2

5
1 2
2 3
1 4
4 5

示例输出 2

Bob

示例输入 3

6
1 2
2 4
5 1
6 3
3 2

示例输出 3

Alice

示例输入 4

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

示例输出 4

Bob