Score : $600$ points

问题描述

对于 $T$ 个测试用例，解决以下问题。

我们有 $N$ 个半开区间 $[L_i, R_i)$（$1 \le i \le N$）。使用这些区间，Alice 和 Bob 将进行以下游戏：

• Alice 和 Bob 交替执行以下操作，Alice 先手：
  • 从 $N$ 个区间中选择一个不与已选择的任何区间相交的区间。

无法执行该操作的玩家输掉比赛，而另一名玩家获胜。
如果两名玩家都采取最优策略来赢得比赛，那么哪位玩家会获胜？

什么是半开区间？ 半开区间 $[X,Y)$ 是指满足 $X \leq x < Y$ 的所有实数 $x$ 构成的区间。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Solve the problem below for $T$ test cases.

We have $N$ half-open intervals $[L_i,R_i)$ ($1 \le i \le N$). Using them, Alice and Bob will play the following game:

• Alice and Bob alternately do the following operation, Alice going first.
  • From the $N$ intervals, choose one that does not intersect with any of the intervals that are already chosen.

The player who gets unable to do the operation loses, and the other player wins.
Which player will win if both players play optimally to win?

What is a half-open interval?A half-open interval $[X,Y)$ is an interval consisting of all real numbers $x$ satisfying $X \leq x < Y$.

Constraints

• All values in input are integers.
• $1 \le T \le 20$
• $1 \le N \le 100$
• $1 \le L_i < R_i \le 100$

Input

Input is given from Standard Input. The first line is in the following format:

$T$

Then, $T$ test cases follow, each of which is in the following format:

$N$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_N$ $R_N$

Output

Print $T$ lines.
The $i$-th line should contain Alice if Alice wins in the $i$-th test case, and Bob if Bob wins.

Sample Input 1

5
3
53 98
8 43
12 53
10
4 7
5 7
3 7
4 5
5 8
6 9
4 8
5 10
1 9
5 10
2
58 98
11 29
6
79 83
44 83
38 74
49 88
18 45
64 99
1
5 9

Sample Output 1

Bob
Alice
Bob
Alice
Alice

This input contains five test cases.

For the first test case, we will show one possible progression of the game below.

• Alice chooses the interval $[12,53)$.
• Bob chooses the interval $[53,98)$. Note that $[12,53)$ and $[53,98)$ do not intersect since they are half-open.
• Alice is unable to do an operation, and Bob wins.

These moves may not be the best choices for them, but we can show that Bob will win if both play optimally.

As seen in the second test case, there can be multiple occurrences of the same interval within a test case.

update @ 2024/3/10 09:19:54