Ася дуже любить тварин. Нещодавно вона придбала \(𝑛\) кошенят, дала їм числові ідентифікатори від 1 до \(𝑛\) і поселила у вольєрі. Вольєр є рядом з \(𝑛\) комірок, також пронумерованих від 1 до \(𝑛 \). Сусідні комірки розділені сітчастими перегородками, всього у вольєрі \(n-1\) перегородок. Спочатку в кожній комірці оселилося рівно одне кошеня з деяким номером.

Спостерігаючи за кошенятами, Ася помітила, що вони дуже доброзичливі і деякі пари кошенят, що живуть у сусідніх комірках, дуже хочуть гратися один з одним. Щоб не позбавляти їх цього задоволення, Ася почала виймати перегородки між сусідніми комірками, роблячи їх більшими.

У \(𝑖\)-й день Ася робила таке.

• Звертала увагу, що якісь кошенята \(𝑥_𝑖\) і \(𝑦_𝑖\) , що в \(𝑖\)-й день живуть у сусідніх комірках, хочуть гратися.
• Видаляла перегородку між цими комірками, перетворюючи їх на одну, в якій опинялися всі кошенята з двох колишніх комірок.

Оскільки Ася не повертала перегородки, через 1 день вольєр став єдиною коміркою, в якому живуть всі кошенята. Будучи дуже педантичною, Ася записувала в спеціальний журнал ідентифікатори кошенят \(𝑥_𝑖\) та \(𝑦_𝑖\) для кожного з \(𝑛−1\) днів.

Вам до рук потрапив журнал із цією інформацією, проте вам невідомо, як кошенята були поселені в комірки спочатку. Знайдіть будь-яке розселення кошенят по \(𝑛\) комірках, що не суперечить даним в журналі.

Формат вхідних даних

У першому рядку задано ціле число \(𝑛\) (\(2≤𝑛≤150000\) ) — кількість кошенят. У наступних \(n-1\) рядках задані пари цілих чисел \(x_i,y_i\) (\(1 \le x_i,y_i \le n\), \(x_i \neq y_i\).

Гарантується, що кошенята \(x_i\) та \(y_i\) не знаходяться в одній комірці за підсумками попередніх об'єднань комірок.

Формат вихідних даних

Виведіть \(𝑛\) різних цілих чисел \(𝑝_𝑖\) (\(1≤𝑝_𝑖≤𝑛 \)), де \(𝑝_𝑖\)  — ідентифікатор кошеняти, яке спочатку жило в комірці з номером \(𝑖\) .

Якщо можливих варіантів відповіді є кілька, виведіть будь-який з них.

Примітка

У відповіді наведено одне з можливих початкових розселень кошенят, існують і інші варіанти відповіді. На зображенні нижче показано, як відбувалося об'єднання комірок цього варіанту розміщення кошенят. Зверніть увагу, що при такому розміщенні кошенята, які подружилися щодня згідно журналу Асі, знаходяться в сусідніх комірках.

Оцінювання

• Рішення, які коректно працюють при \(1≤𝑛≤10\) , наберуть не менше 20 балів.
• Рішення, які коректно працюють при \(1≤𝑛≤100\) , наберуть не менше 40 балів.
• Рішення, які коректно працюють при \(1≤𝑛≤2000\) , наберуть не менше 70 балів.

Приклад вхідних даних

5
1 4
2 5
3 1
4 5

Приклад вихідних даних

3 1 4 2 5