eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Игра на дереве

Игра на дереве

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Алиса и Боб играют в игру на неориентированном дереве. Алиса ходит первой и этим своим ходом она может отметить любую вершину дерева. Далее игроки ходят по очереди. Каждый игрок на своем ходе может выбрать вершину, соседнюю с ПОСЛЕДНЕЙ отмеченной и отметить ее. Игрок не может выбрать уже отмеченную вершину. Если игрок не может выбрать вершину, он проигрывает.

Считая что оба игрока ведут игру оптимально, определите по начальному состоянию игры победителя.

Входные данные

Первая строка содержит количество тестов T. Дальше следует описание самих тестов. Первая строка каждого теста содержит количество вершин в дереве N. Каждая из следующие N-1 строк содержит два целых числа a и b, разделенных пробелом, которые указывают на существование ребра между a и b. (1a, bN).

Известно, что T25, N50000.

Выходные данные

Вывод состоит из T строк. Для каждого теста в отдельной строке следует вывести "Alice", если выиграет Алиса и "Bob" иначе. [кавычки не выводятся].

Пример

Входные данные #1
2
2
1 2
3
1 2
1 3
Выходные данные #1
Bob
Alice
Автор Аджай Сомани
Источник Севастополь - 2010