Гіацинт
Як новий співробітник 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. Дійсні частоти - цілі невід'ємні числа, менші, ніж 10^9.