Задача №113567. Хорватские ученые
Ученые в тайной химической лаборатории в Хорватии изучают химические связи в недавно обнаруженном веществе инопланетного происхождения. Имеющаяся в распоряжении ученых порция вещества состоит из N молекул, соединенных между собой N - 1 ковалентными связями, и все молекулы объединены этими связями (не обязательно напрямую) в единую сеть.
Так как вещество нестабильное, в каждой молекуле регулярно возникают импульсы, перемещающиеся по веществу через существующие связи в обоих направлениях. Ученые собираются стабилизировать вещество, направив ковалентные связи (то есть, дав импульсам возможность путешествовать по ним между молекулами лишь в одном направлении). Показатель нестабильности вещества определяется длиной максимального пути, который может пройти импульс в нем, и ученые хотят сделать эту величину как можно меньше.
Помогите ученым создать вещество с минимальным показателем нестабильности, указав необходимое направление ковалентных связей.
Первая строка содержит одно целое число N ( 2 ≤ N ≤ 100000 ). Каждая из последующих N - 1 строк содержит по два целых числа a i и b i ( 1 ≤ a i , b i ≤ N ), которые показывают что молекулы с номерами a i и b i соединены ковалентной связью.
Выведите N - 1 строку, каждая из которых должна содержать 1 если ковалентная связь должна быть направлена от a i к b i или 0 в противном случае.
Решения, в которых N ≤ 20 , будут оцениваться в 30 баллов.
3 1 2 2 3
0 1
4 2 1 1 3 4 1
1 0 1