有一棵由 $$$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 立即获胜,因为排列已经排序。