Problem
आसिया को जानवरों से बहुत प्यार है। उसने हाल ही में n बिल्ली के बच्चे खरीदे, उन्हें 1 से n तक संख्यात्मक पहचानकर्ता दिए, और उन्हें एक बाड़े में रखा। एवियरी एन कोशिकाओं की एक पंक्ति है, जिसे 1 से एन तक भी गिना जाता है। पड़ोसी कोशिकाओं को जाल विभाजन से अलग किया जाता है, कुल में एन एंड माइनस होते हैं; बाड़े में 1 विभाजन। प्रारंभ में, ठीक एक बिल्ली का बच्चा जिसकी प्रत्येक कोशिका में कुछ संख्या होती है।
बिल्ली के बच्चे को देखते हुए, आसिया ने देखा कि वे बहुत मिलनसार हैं और पड़ोसी कोशिकाओं में रहने वाले कुछ बिल्ली के बच्चे वास्तव में एक दूसरे के साथ खेलना चाहते हैं। उन्हें इस आनंद से वंचित न करने के लिए, आसिया ने आसन्न कोशिकाओं के बीच के विभाजन को हटाना शुरू कर दिया, जिससे वे बड़े हो गए।
पहले-वें दिन, आसिया ने निम्नलिखित किया।
मैंने देखा कि i-वें दिन पड़ोसी कोशिकाओं में रहने वाले कुछ बिल्ली के बच्चे x
i और y
i खेलना चाहते हैं।
मैंने इन कोशिकाओं के बीच के विभाजन को हटा दिया, उन्हें एक में बदल दिया, जिसमें पिछली दो कोशिकाओं के सभी बिल्ली के बच्चे समाप्त हो गए।
चूंकि आसिया ने विभाजन वापस नहीं किया, एन एंड माइनस के बाद; 1 दिन बाड़े में एक एकल कोशिका बन गई जिसमें सभी बिल्ली के बच्चे रहते थे। बहुत पांडित्यपूर्ण होने के कारण, आसिया ने बिल्ली के बच्चे की आईडी x
i and y
i प्रत्येक n−1 दिन के लिए एक विशेष जर्नल में लिख दिया।
आपको इस जानकारी के साथ एक पत्रिका मिली है, लेकिन आप नहीं जानते कि बिल्ली के बच्चे पहली बार कोशिकाओं में कैसे बसे थे। एन मूल कोशिकाओं में बिल्ली के बच्चे का कोई वितरण खोजें जो लॉग में डेटा का खंडन नहीं करता है।
इनपुट
पहली पंक्ति में एक पूर्णांक 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\) ) — बिल्ली के बच्चे के पहचानकर्ता, जिन कोशिकाओं के बीच विभाजन को दिन i पर हटा दिया गया था। यह गारंटी है कि बिल्ली के बच्चे xi और yi पिछले सेल विलय के परिणामस्वरूप एक ही सेल में नहीं हैं।
छाप
प्रिंट एन विशिष्ट पूर्णांक p
i (
\(1 \leq p_i \leq n\)), जहां p
i — बिल्ली के बच्चे का पहचानकर्ता जो मूल रूप से सेल नंबर i में रहता था। यदि कई संभावित उत्तर हैं, तो उनमें से कोई भी प्रिंट करें।
नोट
उत्तर में, उदाहरण के लिए, बिल्ली के बच्चे की संभावित प्रारंभिक बस्तियों में से एक दिया गया है, अन्य उत्तर हैं। नीचे दी गई छवि दिखाती है कि बिल्ली के बच्चे के इस प्रारंभिक प्लेसमेंट के लिए कोशिकाओं को कैसे मर्ज किया गया था। कृपया ध्यान दें कि इस व्यवस्था के साथ, आसिया के जर्नल के अनुसार हर दिन दोस्त बनने वाले बिल्ली के बच्चे आसन्न कोशिकाओं में हैं।
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स">
<शरीर>
| इनपुट |
आउटपुट |
5
14
25
3 1
4 5 |
3 1 4 2 5 |