e-olymp
Задачи

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

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

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

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

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

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

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

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

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

Лимит времени 1 секунда
Лимит использования памяти 256 MiB
Входные данные #1
2
2
1 2
3
1 2
1 3
Выходные данные #1
Bob
Alice

Объяснение: Большой входной файл

Автор Аджай Сомани
Источник Севастополь - 2010