Задача №1821. Незадача
В королевстве, как водится, n городов, соединённых n−1 дорогой. При этом по дорогам можно добраться из любого города до любого другого.
Но вот незадача: король погиб в бою, оставив королевство в наследство двум сыновьям. Теперь им необходимо разделить королевство на две части. Для того, чтобы деление считалось справедливым, было решено:
* Принцы получат наборы городов, отличающиеся количеством не более, чем в два раза.
* Из любого города одного принца останется возможность добраться до любого другого города того же принца по дорогам, соединяющим города этого принца.
Придворный шут заметил, что такое деление не всегда возможно. Голову ему отрубили, но потом задумались... И постановили: один город можно оставить в совместном правлении и считать его принадлежащим и первому, и второму принцу.
В первой строке записано целое число \(n\) — количество городов (2 \(\le\) \(n\) \(\le\) 100000). Каждая из следующих \(n\) − 1 строк содержит по два целых числа — номера городов, соединённых этой дорогой. Города нумеруются с единицы.
Выведите \(n\) целых чисел — для каждого города 1, если им будет править первый принц, 2 — если второй, 0 — если оба. Если ответов несколько, можно выводить любой из них. Ответ существует для любых корректных входных данных.
3 1 2 2 3
2 0 1