← 返回题目列表

Codeforces · 2002/B

B. 移除游戏

中文机器翻译题面 查看原题

Alice 得到了 $$$[1,2,\ldots,n]$$$ 的排列 $$$a_1, a_2, \ldots, a_n$$$,而 Bob 得到了 $$$[1,2,\ldots,n]$$$ 的另一个排列 $$$b_1, b_2, \ldots, b_n$$$。他们将用这些阵列玩一个游戏。

在每一回合中,以下事件按顺序发生:

- Alice 选择数组的第一个或最后一个元素并将其从数组中删除;
- Bob 选择数组的第一个或最后一个元素并将其从数组中删除。

游戏持续 $$$n-1$$$ 回合,之后两个数组都将只有一个剩余元素:数组 $$$a$$$ 中的 $$$x$$$ 和数组 $$$b$$$ 中的 $$$y$$$。

如果$$$x=y$$$,鲍勃获胜;否则,爱丽丝获胜。如果两名玩家都发挥最佳,找出哪位玩家会获胜。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\le t\le10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 3\cdot 10^5$$$)。

下一行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$($$$1\le a_i\le n$$$,所有 $$$a_i$$$ 都是不同的)— Alice 的排列。

下一行包含 $$$n$$$ 整数 $$$b_1,b_2,\ldots,b_n$$$ ($$$1\le b_i\le n$$$,所有 $$$b_i$$$ 都是不同的)— Bob 的排列。

保证所有$$$n$$$的总和不超过$$$3\cdot 10^5$$$。

输出

对于每个测试用例,假设两个玩家都发挥最佳状态,打印一行包含获胜者姓名的行。如果 Alice 获胜,则打印 $$$\texttt{Alice}$$$;否则,打印 $$$\texttt{Bob}$$$。

示例

输入 #1

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

输出 #1

Bob
Alice

注意

在第一个测试用例中,Bob 可以通过删除与 Alice 相同的元素来赢得游戏。

在第二个测试用例中,Alice可以在第一回合中删除$$$3$$$,然后在第二回合中删除与Bob在第一回合中删除的元素不同的元素,从而赢得游戏。