Problem
آسيا تحب الحيوانات كثيرا. اشترت مؤخرًا عدد n من القطط ، وأعطتهم معرفات رقمية من 1 إلى n ، ووضعتهم في حاوية. القفص هو صف من الخلايا n ، مرقمة أيضًا من 1 إلى n. يتم فصل الخلايا المجاورة بواسطة أقسام شبكية ، في المجموع هناك أقسام n & ناقص ؛ 1 في العلبة. في البداية ، استقرت قطة واحدة بالضبط مع عدد معين في كل خلية.
عند مشاهدة القطط الصغيرة ، لاحظت Asya أنها ودودة للغاية وأن بعض أزواج القطط التي تعيش في الخلايا المجاورة تريد حقًا اللعب مع بعضها البعض. من أجل عدم حرمانهم من هذه المتعة ، بدأت Asya في إزالة الفواصل بين الخلايا المجاورة ، وجعلها أكبر.
في اليوم الأول ، قامت آسيا بما يلي.
لقد لاحظت أن بعض القطط x
i و y
i ، تعيش في الخلايا المجاورة في اليوم الأول ، تريد اللعب.
أزلت الحاجز بين هذه الخلايا ، وحولتها إلى خلية واحدة ، انتهى بها المطاف بكل القطط الصغيرة من الخليتين السابقتين.
نظرًا لأن Asya لم تعيد الأقسام ، بعد يوم واحد ، أصبح السياج خلية واحدة تعيش فيها جميع القطط الصغيرة. نظرًا لكونها متحذلقًا للغاية ، فقد كتبت Asya معرّفات القطط x
i & nbsp؛ و y
i & nbsp؛ لكل من n & minus؛ 1 يوم في مجلة خاصة.
لقد حصلت على مجلة بهذه المعلومات ، لكنك لا تعرف كيف استقرت القطط في الزنازين في المقام الأول. ابحث عن أي توزيع للقطط في عدد n من الخلايا الأصلية لا يتعارض مع البيانات الموجودة في السجل.
إدخال
يحتوي السطر الأول على عدد صحيح n ( \ (2 \ leq n \ leq 150000 \) ) & mdash؛ عدد القطط.
السطر التالي n & ناقص؛ 1 يحتوي على أزواج من الأعداد الصحيحة x i ، y i & nbsp؛ (& nbsp؛ \ (1 \ leq x_i ، y_i، \ leq n، x_i \ neq y_i \) & nbsp؛) & [مدش]؛ معرفات القطط ، بين الخلايا التي تمت إزالة القسم منها في اليوم الأول. مضمون أن القطط xi & nbsp؛ و yi & nbsp؛ ليستا في نفس الخلية نتيجة لدمج الخلية سابقًا.
بصمة
طباعة n أعداد صحيحة مميزة p i ( \ (1 \ leq p_i \ leq n \) ) ، حيث p i & [مدش] ؛ معرّف القطة التي عاشت في الأصل في رقم الخلية i. إذا كانت هناك عدة إجابات محتملة ، فقم بطباعة أي منها.
ملاحظة
في الإجابة ، على سبيل المثال ، تم تقديم إحدى التسويات الأولية المحتملة للقطط ، وهناك إجابات أخرى. توضح الصورة أدناه كيف تم دمج الخلايا لهذا الموضع الأولي للقطط. يرجى ملاحظة أنه مع هذا الترتيب ، فإن القطط التي أصبحت صديقة في كل يوم وفقًا لمجلة آسيا موجودة في زنازين مجاورة.
نبسب ؛
<الجسم>
| إدخال
| الإخراج
|
5
14
25
3 1
4 5 |
3 1 4 2 5 |