CF1659F.Tree and Permutation Game

There is a tree of $n$ vertices and a permutation $p$ of size $n$. A token is present on vertex $x$ of the tree.

Alice and Bob are playing a game. Alice is in control of the permutation $p$, and Bob is in control of the token on the tree. In Alice's turn, she must pick two distinct numbers $u$ and $v$ (not positions; $u \neq v$), such that the token is neither at vertex $u$ nor vertex $v$ on the tree, and swap their positions in the permutation $p$. In Bob's turn, he must move the token to an adjacent vertex from the one it is currently on.

Alice wants to sort the permutation in increasing order. Bob wants to prevent that. Alice wins if the permutation is sorted in increasing order at the beginning or end of her turn. Bob wins if he can make the game go on for an infinite number of moves (which means that Alice is never able to get a sorted permutation). Both players play optimally. Alice makes the first move.

Given the tree, the permutation $p$, and the vertex $x$ on which the token initially is, find the winner of the game.

有一棵包含 $n$ 个顶点的树，以及一个长度为 $n$ 的排列 $p$。一个标记（token）初始位于树上的顶点 $x$ 处。

Alice 和 Bob 正在进行一场博弈。Alice 控制排列 $p$，而 Bob 控制树上的标记。在 Alice 的回合中，她必须选择两个互不相同的数 $u$ 和 $v$（注意：这里指的是数值，而非位置；即要求 $u \neq v$），且当前标记既不在顶点 $u$ 上，也不在顶点 $v$ 上，然后在排列 $p$ 中交换 $u$ 和 $v$ 所在的位置。在 Bob 的回合中，他必须将标记从当前所在顶点移动到与其相邻的一个顶点上。

Alice 的目标是将排列 $p$ 变为升序排列。Bob 的目标则是阻止这一目标实现。若在 Alice 的回合开始时或结束时，排列 $p$ 已是升序排列，则 Alice 获胜；若 Bob 能使游戏无限进行下去（即 Alice 永远无法使排列变为升序），则 Bob 获胜。双方均采取最优策略，且 Alice 先手。

给定该树、排列 $p$ 以及标记初始所在的顶点 $x$，请判断博弈的获胜方。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of each test case follows.

The first line of each test case has two integers $n$ and $x$ ($3 \leq n \leq 2 \cdot 10^5$; $1 \leq x \leq n$).

Each of the next $n-1$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \neq b$) indicating an undirected edge between vertex $a$ and vertex $b$. It is guaranteed that the given edges form a tree.

The next line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — the permutation $p$.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, output one line containing Alice or Bob — the winner of the game. The output is case-sensitive.

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

Here is the explanation for the first example:

In the first test case, there is a way for Alice to win. Here is a possible sequence of moves:

1. Alice swaps $5$ and $6$, resulting in $[2,1,3,5,4,6]$.
2. Bob moves the token to vertex $5$.
3. Alice swaps $1$ and $2$, resulting in $[1,2,3,5,4,6]$.
4. Bob moves the token to vertex $3$.
5. Alice swaps $4$ and $5$, resulting in $[1,2,3,4,5,6]$, and wins.

In the second test case, Alice cannot win since Bob can make the game go on forever. Here is the sequence of moves:

1. Alice can only swap $1$ and $3$, resulting in $[3,1,2]$.
2. Bob moves the token to vertex $1$.
3. Alice can only swap $2$ and $3$, resulting in $[2,1,3]$.
4. Bob moves the token to vertex $2$.
5. Alice can only swap $1$ and $3$, resulting in $[2,3,1]$.
6. Bob moves the token to vertex $3$.
7. Alice can only swap $1$ and $2$, resulting in $[1,3,2]$.
8. Bob moves the token to vertex $2$.

And then the sequence repeats forever.

In the third test case, Alice wins immediately since the permutation is already sorted.

以下是第一个示例的解释：

在第一个测试用例中，存在一种 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 立即获胜，因为初始排列已经排好序。