#348. 翻棋游戏 I

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: claude-bot

题目描述

题目描述

在 N\times M 的方阵中每格恰有一枚棋子,给定的 K 枚为黑,其余为白。 Alice 先手,两人轮流操作:选择一枚白色棋子 (x,y) ,把所有满足 1\le i\le x,\ 1\le j\le y 的格子 (i,j) 上的棋子全部翻面(白变黑、黑变白)。 轮到某人时若棋盘上没有白色棋子(无法操作),则该人输。双方均采取最优策略,请输出胜者。

输入格式

第一行一个整数 T ,表示数据组数。 每组数据第一行三个整数 N, M, K ;接下来 K 行每行两个整数 x_i, y_i ,表示一枚黑棋的位置。 坐标互不相同,且 1\le x_i\le N,\ 1\le y_i\le M 。

输出格式

每组数据输出一行 Alice 或 Bob。

样例

样例输入

2
3 3 3
1 1
2 2
3 3
2 2 2
1 2
2 1

样例输出

Bob
Alice

输入格式

第一行一个整数 T ,表示数据组数。 每组数据第一行三个整数 N, M, K ;接下来 K 行每行两个整数 x_i, y_i ,表示一枚黑棋的位置。 坐标互不相同,且 1\le x_i\le N,\ 1\le y_i\le M 。

输出格式

每组数据输出一行 Alice 或 Bob。

样例

样例输入

2
3 3 3
1 1
2 2
3 3
2 2 2
1 2
2 1

样例输出

Bob
Alice

数据范围与提示

数据范围

1\le T\le 10 , 1\le N,M\le 10^9 , 0\le K\le \min(N\cdot M,\ 2\times 10^5) , \sum K\le 2\times 10^5 。

提示

势函数论证游戏必然终止 ⇒ 步数奇偶被初始决定 ⇒ (1,1) 为白 \iff Alice 胜。