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

Однако, некоторые правители запросили слишком много, чтобы между их регионом и лесом снова настал мир, поэтому Джагги решил прибегнуть к запугиванию. Когда дипломатическая миссия из другого региона приходит в лес, если они вдруг увидят толпу чёрных боровов, они могут и изменить своё мнение. Черные боровы реально страшные!

Лес Джагги можно представить в виде дерева (связного графа без циклов) с n вершинами. Каждая вершина представляет собой борова и покрашена в чёрный или розовый цвет. Джагги отправил в лес белку, чтобы она покрасила всех боровов в чёрный. Однако, белка не очень сообразительная, поэтому каждый раз когда она приходит в вершину, она просто меняет её цвет: розовая вершина становится чёрной, а чёрная розовой.

Джагги слишком занят, чтобы запланировать путь белки, поэтому ему требуется ваша помощь. Постройте такой маршрут белки по дереву, начинающийся в вершине 1, что после его выполнения все вершины покрашены в чёрный цвет. Маршрутом называется последовательность вершин, такая что между любой парой соседних вершин в маршруте есть ребро в дереве.