Это простая версия задачи. В этой версии \(\mathbf{u = v}\). Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Алиса и Боб играют в забавную игру на дереве. В эту игру играют на дереве из \(n\) вершин, пронумерованных от \(1\) до \(n\). Напомним, что дерево на \(n\) вершинах — это неориентированный связный граф с \(n - 1\) ребрами.
Алиса и Боб ходят по очереди, причём Алиса ходит первой. Каждый игрок начинает с какой-то вершины.
В свой ход игрок должен перейти из текущей вершины в соседнюю, которая ещё не была никем посещена до этого. Первый игрок, который не может сделать ход, проигрывает.
Вам даны две вершины \(u\) и \(v\). Представим простой путь из вершины \(u\) в \(v\) как массив \(p_1, p_2, p_3, \ldots, p_m\), где \(p_1 = u\), \(p_m = v\), между \(p_i\) и \(p_{i + 1}\) есть ребро для всех \(i\) (\(1 \le i < m\)).
Вы должны определить победителя игры, если Алиса начнёт в вершине \(1\), а Боб в вершине \(p_j\) для каждого \(j\) (где \(1 \le j \le m\)).
Выходные данные
Для каждого набора входных данных выведите \(m\) строк.
В \(i\)-й строке выведите победителя игры, если Алиса начинает с вершины \(1\), а Боб с вершины \(p_i\), выведите «Alice» (без кавычек), если выиграет Алиса, или «Bob» (без кавычек) в противном случае.
Примечание
Дерево из первого и второго примера. В первом наборе входных данных путь будет иметь вид (\(2,2\)). Боб начинает в вершине \(2\), Алиса в своём первом ходу не сможет никуда пойти, и она проиграет.
Во втором наборе входных данных путь будет иметь вид (\(3,3\)). Боб начинает в вершине \(3\), Алиса переместится в вершину \(2\), и у Боба не останется вершин, которые можно посетить, и он проиграет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 2
2 3
2 2
3
1 2
2 3
3 3
6
1 2
1 3
2 4
2 5
1 6
4 4
|
Bob
Alice
Alice
|