Məsələlər
Игра на дереве
Игра на дереве
Алиса и Боб играют в игру на неориентированном дереве. Алиса ходит первой и этим своим ходом она может отметить любую вершину дерева. Далее игроки ходят по очереди. Каждый игрок на своем ходе может выбрать вершину, соседнюю с ПОСЛЕДНЕЙ отмеченной и отметить ее. Игрок не может выбрать уже отмеченную вершину. Если игрок не может выбрать вершину, он проигрывает.
Считая что оба игрока ведут игру оптимально, определите по начальному состоянию игры победителя.
\InputFile
Первая строка содержит количество тестов \textbf{T}. Дальше следует описание самих тестов. Первая строка каждого теста содержит количество вершин в дереве \textbf{N}. Каждая из следующие \textbf{N}-\textbf{1} строк содержит два целых числа \textbf{a} и \textbf{b}, разделенных пробелом, которые указывают на существование ребра между \textbf{a} и \textbf{b}. (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{N}).
Известно, что \textbf{T} ≤ \textbf{25}, \textbf{N} ≤ \textbf{50000}.
\OutputFile
Вывод состоит из \textbf{T} строк. Для каждого теста в отдельной строке следует вывести "\textbf{Alice}", если выиграет Алиса и "\textbf{Bob}" иначе. \[кавычки не выводятся\].
Giriş verilənləri #1
2 2 1 2 3 1 2 1 3
Çıxış verilənləri #1
Bob Alice
Şərh: Большой входной файл