← 返回题目列表

Codeforces · 1823/E

E. 删除图表

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

Alice 和 Bob 正在图表上玩游戏。它们有一个无向图,没有自环和多条边。图的所有顶点的度数都等于 $$$2$$$。该图可能由几个部分组成。请注意,如果这样的图有 $$$n$$$ 个顶点,那么它将恰好有 $$$n$$$ 个边。

Alice 和 Bob 轮流。爱丽丝先走。在每一回合中,玩家可以选择 $$$k$$$ ($$$l \le k \le r$$$; $$$l < r$$$) 顶点形成连通子图,并从图中删除这些顶点,包括所有关联边。

无法迈出一步的玩家失败。

例如,假设他们在给定的图表上玩给定的 $$$l = 2$$$ 和 $$$r = 3$$$:

Alice 在第一次移动时选择的有效顶点集是以下之一:

- $$$\{1, 2\}$$$
- $$$\{1, 3\}$$$
- $$$\{2, 3\}$$$
- $$$\{4, 5\}$$$
- $$$\{4, 6\}$$$
- $$$\{5, 6\}$$$
- $$$\{1, 2, 3\}$$$
- $$$\{4, 5, 6\}$$$

那么鲍勃在第一次移动时选择的有效顶点集是以下之一:

- $$$\{1, 2\}$$$
- $$$\{1, 3\}$$$
- $$$\{2, 3\}$$$
- $$$\{1, 2, 3\}$$$

Alice无法移动,所以她输了。

给你一个大小为 $$$n$$$ 和整数 $$$l$$$ 和 $$$r$$$ 的图表。如果爱丽丝和鲍勃都发挥最佳,谁会获胜。

输入

第一行包含三个整数 $$$n$$$、$$$l$$$ 和 $$$r$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$1 \le l < r \le n$$$) - 图中的顶点数,以及 Alice 或 Bob 在一次移动中可以选择的顶点数的约束。

接下来的 $$$n$$$ 行包含图形的边:每行一个边。第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) - 第 $$$i$$$ 边的描述。

保证给定图的每个顶点的度等于$$$2$$$。

输出

如果 Alice 获胜,则打印 Alice(不区分大小写),否则打印 Bob。

示例

输入 #1

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

输出 #1

Bob

输入 #2

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

输出 #2

Bob

输入 #3

12 1 3
1 2
2 3
3 1
4 5
5 6
6 7
7 4
8 9
9 10
10 11
11 12
12 8

输出 #3

Alice

注意

在第一个测试中,显示了与图例中相同的输入。

在第二个测试中,显示了与图例中相同的图表,但 $$$l = 1$$$ 和 $$$r = 2$$$。