Masala E

Ko'rsichqonlar — tartibni yaxshi ko‘radigan va mehnatkash hayvonlardir. Bizning ko'rsichqon esa o‘z yer osti uyini juda tartibli holatda saqlashni yoqtiradi, shunda u yerda yashovchi har bir kishi kerakli narsani oson topa oladi.

Shu maqsadda, ko'rsichqon xonalarni shunday tunnellar bilan bog‘ladiki, har qanday ikkita xona orasida faqat bitta yagona yo‘l mavjud.

Ikki xona orasidagi masofa — ular orasidagi yo‘lda o‘tilgan tunnel soni sifatida aniqlanadi.

Shuncha mehnatga qaramay, ko'rsichqonning ba’zi mehmonlari ayrim xonalar orasida yurish juda uzoq vaqt olishini aytib shikoyat qilmoqda.

Shuning uchun ko'rsichqon uyini qayta qurishga qaror qildi:

• bir tunnelni yopadi,
• yangi bir tunnelni ochadi,
  shunda ikki eng uzoq joylashgan xona orasidagi masofa imkon qadar kichik bo‘ladi.

Barcha xonalar hali ham bir-biriga bog‘langan bo‘lib qolishi kerak (ya’ni, har bir xonadan har bir boshqa xonaga yetib borish mumkin bo‘lishi kerak).

Birinchi qatorda bitta butun son $N (1 \le N \le 3 \times 10^5)$— xonalar soni beriladi. Xonalar $1$ dan $N$ gacha raqamlangan.

Keyingi $N−1$ ta qatorda har birida ikkita butun son beriladi — bu sonlar o‘zaro tunnel bilan bog‘langan xonalar raqami.

Uchta qator chiqaring:

1. Eng uzoq joylashgan xonalar orasidagi yangi masofa (rekonstruksiyadan so‘ng).
2. Yopilishi kerak bo‘lgan tunnelni bildiruvchi ikkita xona raqami.
3. Yangi ochilishi kerak bo‘lgan tunnelni bildiruvchi ikkita xona raqami.

Eslatma: Yechim yagona bo‘lmasligi mumkin. Har qanday rekonstruksiya rejasi qabul qilinadi, agar u masofani minimal qilsa.