#P18579. Combination Locks

Combination Locks

Combination Locks

Alice 和 Bob 各有一把密码锁,每把锁由 N 个转盘组成,每个转盘上有 0 到 9 十个数字。没有密码锁的 Charlie 为他们设计了一个游戏。

Charlie 只记录两把锁对应位置上的数字是否相同,并用一个长度为 N 的差异模式 S 表示当前状态。若两把锁第 j 位的数字相同,S 的第 j 个字符为 =;否则为 .。

Alice 和 Bob 轮流操作,由 Alice 先手。每次操作,当前玩家必须改变自己密码锁的一个数字,并满足以下条件:

  1. 操作后的差异模式必须发生变化。
  2. 操作后的差异模式不能在 Charlie 给出的禁用模式列表中。
  3. 游戏过程中,任何差异模式都不能重复出现。初始差异模式也算已经出现。

无法进行合法操作的玩家输掉游戏。双方都采用最优策略,请判断获胜者。

输入格式

第一行包含测试用例数 T。

每个测试用例的第一行包含两个整数 N 和 C,分别表示密码锁的位数和禁用模式的数量。

接下来两行分别给出 Alice 和 Bob 的初始密码。每行都是由 N 个十进制数字组成的字符串,允许有前导零。

随后 C 行,每行给出一个长度为 N、仅包含 = 和 . 的禁用模式。

保证同一测试用例中的禁用模式互不相同,且初始密码对应的差异模式不在禁用列表中。

输出格式

对于每个测试用例,输出一行获胜者的名字:Alice 或 Bob。区分大小写。

数据范围

  • 1 ≤ T ≤ 20。
  • 1 ≤ N ≤ 10。
  • 0 ≤ C ≤ 1000。

原题没有对所有测试用例的 N 或 C 的总和附加限制。

样例输入 1

3
2 2
12
89
=.
==
3 1
204
101
.==
3 2
000
000
...
==.

样例输出 1

Alice
Bob
Bob

样例说明

第一个测试用例中,Alice 唯一合法的操作是将自己的第二个数字从 2 改成 9。其他操作要么不改变差异模式,要么得到禁用模式。随后 Bob 无法合法操作,因此 Alice 获胜。