区间游戏 2

题目描述

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

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

Alice 先手，两人轮流执行以下操作：

• 从 $N$ 个区间中，选择一个与所有已选区间都没有公共点的区间。

无法进行操作的玩家输掉游戏，另一方获胜。

双方都以获胜为目标采取最优策略时，谁会赢？

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

输入格式

输入按以下格式从标准输入给出。第一行如下：

T

接下来有 $T$ 个测试用例，每个测试用例的格式如下：

N
L_1 R_1
L_2 R_2
⋮
L_N R_N

输出格式

共输出 $T$ 行。

其中第 $i$ 行输出第 $i$ 个测试用例的结果：Alice 赢则输出 Alice，Bob 赢则输出 Bob。

样例

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

Bob
Alice
Bob
Alice
Alice

这个输入包含 5 个测试用例。

关于第 1 个测试用例，下面展示一种可能的游戏过程。

Alice 选择区间 $[12,53)$。

Bob 选择区间 $[53,98)$。由于游戏中使用的区间是半开区间，$[12,53)$ 和 $[53,98)$ 没有公共点。

Alice 无法再进行操作，输掉游戏。Bob 获胜。

对于这个测试用例，上面的步骤不一定对双方都是最优的，但可以证明双方都采取最优策略时，Bob 会获胜。

如第 2 个测试用例所示，一个测试用例中可能包含多个相同的区间。

数据范围

• $1 \le T \le 20$
• $1 \le N \le 100$
• $1 \le L_i \lt R_i \le 100$
• 输入均为整数