Problem
آسیا حیوانات را بسیار دوست دارد. او اخیراً n بچه گربه خریده، به آنها شناسه های عددی از 1 تا n داده و آنها را در یک محفظه قرار داده است. پرندگان یک ردیف از n سلول است که از 1 تا n نیز شماره گذاری شده است. سلول های همسایه با پارتیشن های مش از هم جدا می شوند، در مجموع n و منهای 1 پارتیشن در محفظه وجود دارد. در ابتدا دقیقاً یک بچه گربه با تعداد کمی در هر سلول ساکن شد.
آسیا با تماشای بچه گربه ها متوجه شد که آنها بسیار دوستانه هستند و برخی از جفت های بچه گربه که در سلول های همسایه زندگی می کنند واقعاً می خواهند با یکدیگر بازی کنند. برای اینکه آنها را از این لذت محروم نکند، آسیا شروع به برداشتن پارتیشن های بین سلول های مجاور و بزرگتر کردن آنها کرد.
در روز i ام، آسیا کارهای زیر را انجام داد.
متوجه شدم که برخی از بچه گربه‌های x
i و y
i که در روز i در سلول‌های همسایه زندگی می‌کنند، می‌خواهند بازی کنند.
من پارتیشن بین این سلول ها را برداشتم و آنها را به یکی تبدیل کردم که تمام بچه گربه های دو سلول قبلی در آن قرار گرفتند.
از آنجایی که آسیا پارتیشن ها را برنگرداند، پس از 1 روز، محفظه تبدیل به یک سلول واحد شد که همه بچه گربه ها در آن زندگی می کردند. آسیا از آنجایی که بسیار متحجر بود، شناسه های بچه گربه x
i و y
i برای هر یک از n−1 روز را در یک مجله مخصوص یادداشت کرد.
شما مجله ای با این اطلاعات دریافت کردید، اما نمی دانید که چگونه بچه گربه ها در ابتدا در سلول ها مستقر شدند. هر توزیعی از بچه گربه ها را در n سلول اصلی پیدا کنید که با داده های موجود در گزارش مغایرت نداشته باشد.
ورودی
خط اول شامل یک عدد صحیح n (
\(2 \leq n \leq 150000\)) — تعداد بچه گربه ها.
n−1 خط بعدی شامل جفت اعداد صحیح x
i , y
i (
\(1 \leq x_i است , y_i, \leq n,x_i \neq y_i\) ) — شناسه بچه گربه ها، که پارتیشن بین سلول های آنها در روز اول حذف شد. تضمین شده است که بچه گربه‌های xi و yi در نتیجه ادغام سلول‌های قبلی در یک سلول نیستند.
حصر
چاپ n عدد صحیح مجزا p
i (
\(1 \leq p_i \leq n\))، جایی که p
i — شناسه بچه گربه ای که در ابتدا در سلول شماره i زندگی می کرد. اگر چندین پاسخ ممکن وجود دارد، هر یک از آنها را چاپ کنید.
توجه
در پاسخ به عنوان مثال یکی از اسکان اولیه احتمالی بچه گربه ها آورده شده است، پاسخ های دیگری نیز وجود دارد. تصویر زیر نشان می دهد که چگونه سلول ها برای این قرارگیری اولیه بچه گربه ها ادغام شدند. لطفا توجه داشته باشید که با این ترتیب، بچه گربه هایی که طبق مجله آسیا هر روز با هم دوست می شوند، در سلول های مجاور هستند.
<بدن>
| ورودی |
خروجی |
5
14
25
3 1
4 5 |
3 1 4 2 5 |