Я вижу розового борова и хочу покрасить его в чёрный. Чёрные боровы выглядят гораздо круче и брутальнее, чем розовые. Поскольку Джагги теперь правитель леса, он хочет улучшить дипломатические отношения с соседними регионами.
Однако, некоторые правители запросили слишком много, чтобы между их регионом и лесом снова настал мир, поэтому Джагги решил прибегнуть к запугиванию. Когда дипломатическая миссия из другого региона приходит в лес, если они вдруг увидят толпу чёрных боровов, они могут и изменить своё мнение. Черные боровы реально страшные!
Лес Джагги можно представить в виде дерева (связного графа без циклов) с n вершинами. Каждая вершина представляет собой борова и покрашена в чёрный или розовый цвет. Джагги отправил в лес белку, чтобы она покрасила всех боровов в чёрный. Однако, белка не очень сообразительная, поэтому каждый раз когда она приходит в вершину, она просто меняет её цвет: розовая вершина становится чёрной, а чёрная розовой.
Джагги слишком занят, чтобы запланировать путь белки, поэтому ему требуется ваша помощь. Постройте такой маршрут белки по дереву, начинающийся в вершине 1, что после его выполнения все вершины покрашены в чёрный цвет. Маршрутом называется последовательность вершин, такая что между любой парой соседних вершин в маршруте есть ребро в дереве.
Выходные данные
Выведите путь белки как последовательность индексов вершин в порядке посещения. Если все вершины изначально чёрные, то выведите 1. Гарантируется, что решение всегда существует. Если существует несколько решений, выведите любое из них длиной не более 107.