В качестве нового сотрудника в Northwestern Europe Routing Company (NWERC) Вы много размышляете об архитектурах беспроводных сетей. В последнее время Вы узнали о многоканальной архитектуре ячеистой сети (называемой Гиацинт), который снабжает каждый сетевой узел сетью несколькими картами сетевого интерфейса (КСИ) для увеличения пропускной способности сети. Вы можете выбрать частоту канала для каждого сетевого адаптера. Для связи, для каждых двух сетевых узлов, находящихся в зоне действия друг друга, их сетевые карты должны иметь по крайней мере одну общую частоту. Теоретическая пропускная способность является оптимальной, когда общее количество используемых частот в сети максимально.

Ваши руководители в NWERC хотят, чтобы Вы выполнили процедуру присвоения частот NIC таким образом, чтобы количество используемых частот было максимальным, с учетом ограничения для всех пар соседних узлов. Частота считается используемой, если любая пара узлов в диапазоне друг от друга разделяет эту частоту. В сетчатой сети, с которой вы будете иметь дело, каждый узел оснащен ровно двумя сетевыми картами (то есть каждый узел может использовать не более двух частот). Поскольку вы новичок в NWERC, ваши боссы дополнительно ограничивают сетевые макеты, чтобы упростить вашу работу: сетевой график будет формировать дерево.

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

Состоит из:

• строка содержит число n (2 ≤ n ≤ 10000) - количество вершин в сети;

• n - 1 строк, каждое содержит два числа i и j, где 1 ≤ i, j ≤ n, означающие что вершины i и j находятся в зоне действия друг друга.

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

Выведите частотное присвоение для каждого из 2n КСИ, чтобы все соседние узлы могли связываться и количество используемых частот было максимальным. Вы должны вывести n строк, где i - ая строка содержит две частоты сетевого узла i. Действительные частоты - целые неотрицательные числа, меньшие, чем 109.