eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

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

Giriş verilənləri

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

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
2
2
1 2
3
1 2
1 3
Çıxış verilənləri #1
Bob
Alice
Müəllif Аджай Сомани
Mənbə Севастополь - 2010