← 返回题目列表

Codeforces · 1659/F

F. 树和排列游戏

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

有一棵由 $$$n$$$ 个顶点组成的树和一个大小为 $$$n$$$ 的排列 $$$p$$$。树的顶点 $$$x$$$ 上存在令牌。

Alice 和 Bob 正在玩游戏。 Alice 控制着排列 $$$p$$$,Bob 控制着树上的令牌。轮到 Alice 时,她必须选择两个不同的数字 $$$u$$$ 和 $$$v$$$ (不是位置;$$$u \neq v$$$),这样令牌既不在树上的顶点 $$$u$$$ 也不在顶点 $$$v$$$,并交换它们在排列 $$$p$$$ 中的位置。轮到鲍勃时,他必须将令牌从当前所在的顶点移动到相邻的顶点。

Alice 想要按升序对排列进行排序。鲍勃想阻止这种情况发生。如果排列在她的回合开始或结束时按升序排序,则爱丽丝获胜。如果鲍勃能让游戏继续进行无限次移动(这意味着爱丽丝永远无法获得排序排列),那么他就获胜。两名球员都发挥最佳。爱丽丝迈出了第一步。

给定树、排列 $$$p$$$ 以及令牌最初所在的顶点 $$$x$$$,找到游戏的获胜者。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。每个测试用例的描述如下。

每个测试用例的第一行有两个整数 $$$n$$$ 和 $$$x$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq x \leq n$$$)。

接下来的 $$$n-1$$$ 行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \neq b$$$),表示顶点 $$$a$$$ 和顶点 $$$b$$$ 之间的无向边。保证给定的边形成一棵树。

下一行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — 排列 $$$p$$$。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一行包含 Alice 或 Bob(游戏获胜者)的行。输出区分大小写。

示例

输入 #1

3
6 3
1 3
3 2
4 3
3 6
5 3
2 1 3 6 4 5
3 2
1 2
3 2
1 3 2
3 2
1 2
3 2
1 2 3

输出 #1

Alice
Bob
Alice

输入 #2

1
11 4
3 11
5 9
10 3
4 8
2 4
1 8
6 8
8 7
4 5
5 11
7 4 9 8 6 5 11 10 2 3 1

输出 #2

Alice

注意

这是第一个示例的解释:

在第一个测试用例中,Alice 有一种获胜的方法。以下是可能的动作顺序:

1. Alice 交换 $$$5$$$ 和 $$$6$$$,得到 $$$[2,1,3,5,4,6]$$$。
2. Bob 将令牌移动到顶点 $$$5$$$。
3. Alice 交换 $$$1$$$ 和 $$$2$$$,得到 $$$[1,2,3,5,4,6]$$$。
4. Bob 将令牌移动到顶点 $$$3$$$。
5. Alice 交换 $$$4$$$ 和 $$$5$$$,得到 $$$[1,2,3,4,5,6]$$$,并获胜。

在第二个测试用例中,Alice 无法获胜,因为 Bob 可以让游戏永远继续下去。以下是动作顺序:

1. Alice 只能交换 $$$1$$$ 和 $$$3$$$,得到 $$$[3,1,2]$$$。
2. Bob 将令牌移动到顶点 $$$1$$$。
3. Alice 只能交换 $$$2$$$ 和 $$$3$$$,结果是 $$$[2,1,3]$$$。
4. Bob 将令牌移动到顶点 $$$2$$$。
5. Alice 只能交换 $$$1$$$ 和 $$$3$$$,结果是 $$$[2,3,1]$$$。
6. Bob 将令牌移动到顶点 $$$3$$$。
7. Alice 只能交换 $$$1$$$ 和 $$$2$$$,结果是 $$$[1,3,2]$$$。
8. Bob 将令牌移动到顶点 $$$2$$$。

在第三个测试用例中,Alice 立即获胜,因为排列已经排序。