F. Игра с деревом и перестановкой
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть дерево из $$$n$$$ вершин и перестановка $$$p$$$ из $$$n$$$ чисел. В вершине $$$x$$$ дерева находится фишка.

Алиса и Боб играют в игру. Алиса управляет перестановкой $$$p$$$, а Bob управляет фишкой на дереве. В свой ход Алиса обязана выбрать два различных числа $$$u$$$ и $$$v$$$ (не индексы; $$$u \neq v$$$) такие, что фишка не находится ни в вершине $$$u$$$, ни в вершине $$$v$$$ дерева, и поменять их местами в перестановке $$$p$$$. В свой ход Боб обязан передвинуть фишку в соседнюю с текущей вершину.

Алиса хочет отсортировать перестановку в порядке возрастания, Боб хочет помешать этому. Алиса выигрывает, если перестановка отсортирована по возрастанию в начале или в конце ее хода. Боб выигрывает, если он может сделать так, чтобы игра продолжалась бесконечное количество ходов (то есть чтобы Алиса никогда не могла бы получить отсортированную перестановку). Оба игрока играют оптимально. Алиса ходит первой.

По данному дереву, перестановке $$$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 — победителя игры. В ответе важен регистр букв.

Примеры
Входные данные
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
Выходные данные
Alice
Bob
Alice
Входные данные
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
Выходные данные
Alice
Примечание

Ниже находится объяснение первого примера.

В первом наборе входных данных Алиса может выиграть. Например, возможна такая последовательность ходов:

  1. Алиса меняет местами $$$5$$$ и $$$6$$$, получается $$$[2,1,3,5,4,6]$$$.
  2. Боб передвигает фишку в вершину $$$5$$$.
  3. Алиса меняет местами $$$1$$$ и $$$2$$$, получается $$$[1,2,3,5,4,6]$$$.
  4. Боб передвигает фишку в вершину $$$3$$$.
  5. Алиса меняет местами $$$4$$$ и $$$5$$$, получается $$$[1,2,3,4,5,6]$$$ и выигрывает.

Во втором наборе входных данных Алиса не может выиграть, так как Боб может бесконечно долго затягивать игру. Например, возможна такая последовательность ходов:

  1. Алиса меняет местами $$$1$$$ и $$$3$$$, получается $$$[3,1,2]$$$.
  2. Боб передвигает фишку в вершину $$$1$$$.
  3. Алиса меняет местами $$$2$$$ и $$$3$$$, получается $$$[2,1,3]$$$.
  4. Боб передвигает фишку в вершину $$$2$$$.
  5. Алиса меняет местами $$$1$$$ и $$$3$$$, получается $$$[2,3,1]$$$.
  6. Боб передвигает фишку в вершину $$$3$$$.
  7. Алиса меняет местами $$$1$$$ и $$$2$$$, получается $$$[1,3,2]$$$.
  8. Боб передвигает фишку в вершину $$$2$$$.
И далее последовательность бесконечно повторяется.

В третьем наборе Алиса выигрывает сразу, так перестановка уже отсортирована.