310373: CF1823E. Removing Graph

E. Removing Graphtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Alice and Bob are playing a game on a graph. They have an undirected graph without self-loops and multiple edges. All vertices of the graph have degree equal to $2$. The graph may consist of several components. Note that if such graph has $n$ vertices, it will have exactly $n$ edges.

Alice and Bob take turn. Alice goes first. In each turn, the player can choose $k$ ($l \le k \le r$; $l < r$) vertices that form a connected subgraph and erase these vertices from the graph, including all incident edges.

The player who can't make a step loses.

For example, suppose they are playing on the given graph with given $l = 2$ and $r = 3$:

A valid vertex set for Alice to choose at the first move is one of the following:

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

Suppose, Alice chooses subgraph $\{4, 6\}$.

Then a valid vertex set for Bob to choose at the first move is one of the following:

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

Suppose, Bob chooses subgraph $\{1, 2, 3\}$.

Alice can't make a move, so she loses.

You are given a graph of size $n$ and integers $l$ and $r$. Who will win if both Alice and Bob play optimally.

Input

The first line contains three integers $n$, $l$ and $r$ ($3 \le n \le 2 \cdot 10^5$; $1 \le l < r \le n$) — the number of vertices in the graph, and the constraints on the number of vertices Alice or Bob can choose in one move.

Next $n$ lines contains edges of the graph: one edge per line. The $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$; $u_i \neq v_i$) — description of the $i$-th edge.

It's guaranteed that the degree of each vertex of the given graph is equal to $2$.

Output

Print Alice (case-insensitive) if Alice wins, or Bob otherwise.

ExamplesInput

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

Output

Bob

Input

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

Output

Bob

Input

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

Output

Alice

Note

In the first test the same input as in legend is shown.

In the second test the same graph as in legend is shown, but with $l = 1$ and $r = 2$.

题意翻译

# 移除图 ## 题目描述 Alice 和 Bob 在一张图上玩游戏。给定一个无向图，图中的每个顶点的度数都等于 2，不存在自环和重边。该图可能由多个连通分量组成。注意，如果该图有 $ n $ 个顶点，则它一定有 $ n $ 条边。 Alice 和 Bob 轮流进行操作。Alice 先开始。在每一轮中，玩家可以选择一个包含 $ k $ 个顶点的连通子图（$ l \leq k \leq 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\} $ 假设 Alice 移除子图 $ \{4, 6\} $，则 Bob 第一次移除的有效顶点集可以是以下之一： - $ \{1, 2\} $ - $ \{1, 3\} $ - $ \{2, 3\} $ - $ \{1, 2, 3\} $ 假设 Bob 移除子图 $ \{1, 2, 3\} $，Alice 无法进行操作，所以 Alice 失败。 给定一个大小为 $ n $ 的图和整数 $ l $ 和 $ r $。如果 Alice 和 Bob 都采取最优策略，谁将获胜。 ## 输入格式 第一行包含三个整数 $ n $、$ l $ 和 $ r $（$ 3 \leq n \leq 2 \cdot 10^5 $，$ 1 \leq l < r \leq n $），表示图中的顶点数以及 Alice 或 Bob 可以在一次操作中选择的顶点数的约束。 接下来的 $ n $ 行描述图的边：每行包含两个整数 $ u_i $ 和 $ v_i $（$ 1 \leq u_i, v_i \leq n $，$ u_i \neq v_i $），表示第 $ i $ 条边的描述。 保证给定图的每个顶点的度数都等于 2。 ## 输出格式 如果 Alice 获胜，则输出 Alice（不区分大小写），否则输出 Bob。 ## 样例 #1 ### 样例输入 #1 ``` 6 2 3 1 2 2 3 3 1 4 5 5 6 6 4 ``` ### 样例输出 #1 ``` Bob ``` ## 样例 #2 ### 样例输入 #2 ``` 6 1 2 1 2 2 3 3 1 4 5 5 6 6 4 ``` ### 样例输出 #2 ``` Bob ``` ## 样例 #3 ### 样例输入 #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 $。