F. Игра в сокращение дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру на дереве из $$$n$$$ вершин. Алиса ходит первой, после чего игроки ходят по очереди.

В каждый момент у дерева есть выделенный корень. Пусть текущим корнем является $$$u$$$. В свой ход игрок должен выбрать ребёнка $$$v$$$ вершины $$$u$$$ и выполнить ровно одну из следующих операций:

  1. Сделать $$$v$$$ новым корнем.
  2. Удалить всё поддерево$$$^{\text{∗}}$$$ с корнем в $$$v$$$.

Здесь отношения родитель—ребёнок определяются относительно текущего корня.

За всю игру каждая вершина может стать корнем не более одного раза.

Если игрок не может сделать допустимый ход, он проигрывает.

Перед началом игры в качестве компенсации за второй ход Боб может выбрать любую вершину в качестве исходного корня.

По данному дереву определите победителя при условии, что оба игрока действуют оптимально. Если Боб может победить, выведите все вершины, которые он может выбрать в качестве исходного корня, чтобы гарантировать победу, в порядке возрастания.

$$$^{\text{∗}}$$$Поддерево с корнем в вершине $$$v$$$ представляет собой множество всех вершин, путь от которых до корня проходит через $$$v$$$ (включая саму $$$v$$$).

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — количество вершин в дереве.

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$), обозначающих ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что данный граф является деревом.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

Выходные данные
  • Если побеждает Алиса, выведите Alice.
  • В противном случае в первой строке выведите Bob. Во второй строке выведите целое число $$$k$$$ — количество вершин, которые Боб может выбрать в качестве исходного корня, чтобы гарантировать свою победу. В третьей строке выведите $$$k$$$ различных целых чисел $$$v_1,v_2,\ldots,v_k$$$ в порядке возрастания, обозначающих все такие вершины.
Пример
Входные данные
6
2
1 2
3
1 2
2 3
5
1 2
1 3
1 4
1 5
5
1 2
2 3
3 4
4 5
7
1 2
2 3
1 4
4 5
1 6
6 7
7
1 2
1 3
2 4
2 5
3 6
3 7
Выходные данные
Alice
Bob
1
2
Bob
1
1
Bob
2
2 4
Bob
3
2 4 6
Bob
1
1
Примечание

В первом наборе входных данных независимо от того, какую вершину Боб выберет в качестве исходного корня, Алиса может удалить единственное дочернее поддерево первым ходом. После этого Боб не сможет сделать допустимый ход, поэтому победит Алиса.

В пятом наборе входных данных вершины $$$2$$$, $$$4$$$ и $$$6$$$ являются выигрышными вариантами для Боба. Разберём вершину $$$2$$$; два других случая симметричны.

Если Боб выбирает вершину $$$2$$$ в качестве исходного корня, её детьми являются $$$1$$$ и $$$3$$$.

  • Если Алиса меняет корень с $$$2$$$ на $$$1$$$, Боб может поменять корень с $$$1$$$ на $$$4$$$ (или $$$6$$$).
  • Если Алиса удаляет поддерево с корнем в $$$1$$$, Боб удаляет поддерево с корнем в $$$3$$$, после чего Алиса не может сделать допустимый ход.
  • Если Алиса меняет корень с $$$2$$$ на $$$3$$$, Боб удаляет поддерево с корнем в $$$2$$$, после чего Алиса снова не может сделать допустимый ход.
  • Если Алиса удаляет поддерево с корнем в $$$3$$$, Боб удаляет поддерево с корнем в $$$1$$$.

Таким образом, если исходным корнем является $$$2$$$, Боб может гарантировать победу. По симметрии это также верно для $$$4$$$ и $$$6$$$. Если Боб выберет одну из вершин $$$1$$$, $$$3$$$, $$$5$$$ или $$$7$$$, у Алисы будет выигрышная стратегия. Следовательно, ответ — $$$2,4,6$$$.