9399: ABC206 —— F - Interval Game 2
[Creator : ]
Description
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$.
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$.
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$
```
```
$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.
The $i$-th line should contain `Alice` if Alice wins in the $i$-th test case, and `Bob` if Bob wins.
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$
- $1 \le T \le 20$
- $1 \le N \le 100$
- $1 \le L_i < R_i \le 100$
Sample 1 Input
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 1 Output
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.
As seen in the second test case, there can be multiple occurrences of the same interval within a test case.
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.
As seen in the second test case, there can be multiple occurrences of the same interval within a test case.