F - 区间游戏 2

分数：600分

问题描述

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

我们有$N$个左闭右开区间$[L_i,R_i)$（$1 \le i \le N$）。利用这些区间，Alice和Bob将玩下面的游戏：

• Alice和Bob轮流进行以下操作，Alice先行。
  • 从$N$个区间中选择一个，该区间与已经选择的区间不相交。

如果无法进行操作的玩家输掉比赛，另一位玩家胜利。
如果两位玩家都采用最佳策略进行游戏，谁会获胜？

什么是左闭右开区间？

左闭右开区间$[X,Y)$是一个区间，其中$x$是满足$X \leq x < Y$的所有实数。

约束

• 所有输入值均为整数。
• $1 \le T \le 20$
• $1 \le N \le 100$
• $1 \le L_i < R_i \le 100$

---

输入

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

$T$

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

``` $N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$ ```

输出

输出应该包含$T$行。
第$i$行应该包含Alice，如果Alice在第$i$个测试用例中获胜，应该输出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

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

对于第一个测试用例，我们将展示一种可能的游戏进程。

• Alice选择区间$[12,53)$。
• Bob选择区间$[53,98)$。注意，$[12,53)$和$[53,98)$不相交，因为它们是左闭右开的。
• Alice无法进行操作，Bob获胜。

这些行动可能不是他们的最佳选择，但我们可以证明如果两个玩家都采用最佳策略，Bob将会获胜。

正如第二个测试用例所示，一个测试用例中可能会出现多个相同的区间。