Есть дерево из \(n\) вершин и перестановка \(p\) из \(n\) чисел. В вершине \(x\) дерева находится фишка.
Алиса и Боб играют в игру. Алиса управляет перестановкой \(p\), а Bob управляет фишкой на дереве. В свой ход Алиса обязана выбрать два различных числа \(u\) и \(v\) (не индексы; \(u \neq v\)) такие, что фишка не находится ни в вершине \(u\), ни в вершине \(v\) дерева, и поменять их местами в перестановке \(p\). В свой ход Боб обязан передвинуть фишку в соседнюю с текущей вершину.
Алиса хочет отсортировать перестановку в порядке возрастания, Боб хочет помешать этому. Алиса выигрывает, если перестановка отсортирована по возрастанию в начале или в конце ее хода. Боб выигрывает, если он может сделать так, чтобы игра продолжалась бесконечное количество ходов (то есть чтобы Алиса никогда не могла бы получить отсортированную перестановку). Оба игрока играют оптимально. Алиса ходит первой.
По данному дереву, перестановке \(p\) и вершине \(x\), в которой изначально находится фишка, определите победителя игры.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую слово Alice или Bob — победителя игры. В ответе важен регистр букв.
Примечание
Ниже находится объяснение первого примера.
В первом наборе входных данных Алиса может выиграть. Например, возможна такая последовательность ходов:
- Алиса меняет местами \(5\) и \(6\), получается \([2,1,3,5,4,6]\).
- Боб передвигает фишку в вершину \(5\).
- Алиса меняет местами \(1\) и \(2\), получается \([1,2,3,5,4,6]\).
- Боб передвигает фишку в вершину \(3\).
- Алиса меняет местами \(4\) и \(5\), получается \([1,2,3,4,5,6]\) и выигрывает.
Во втором наборе входных данных Алиса не может выиграть, так как Боб может бесконечно долго затягивать игру. Например, возможна такая последовательность ходов:
- Алиса меняет местами \(1\) и \(3\), получается \([3,1,2]\).
- Боб передвигает фишку в вершину \(1\).
- Алиса меняет местами \(2\) и \(3\), получается \([2,1,3]\).
- Боб передвигает фишку в вершину \(2\).
- Алиса меняет местами \(1\) и \(3\), получается \([2,3,1]\).
- Боб передвигает фишку в вершину \(3\).
- Алиса меняет местами \(1\) и \(2\), получается \([1,3,2]\).
- Боб передвигает фишку в вершину \(2\).
И далее последовательность бесконечно повторяется.
В третьем наборе Алиса выигрывает сразу, так перестановка уже отсортирована.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|
Alice
|