Masala #A3OIKNFFXV
Azimjon va daraxt
Azimjon daraxtlarga qiziqganligi sababli, hozida daraxtlar mavzusini o'rganmoqda. U bir qiziqarli masalaga duch keldi, masala sharti quyidagicha:
Uchlari \(1\) dan \(n\) gacha raqamlangan daraxt berilgan bo'lib, qirralari soni \(n-1\) ta. Masalaning asosiy sharti daraxtdan shunday ikki uchni aniqlash kerakki bu uchlar o'rtasidagi masofada maksimal sonda qirralar mavjud bo'lsin.
Azimjon daraxtlar mavzusini endi o'rganayotganligi sababli ushbu masalani yechida qiynalayabdi. Siz Azimjonga yordam beraolasizmi?
Kirish faylining dastlabki satrida \(n(2\leq n\leq 10^5)\) butun soni, daraxt uchlari soni. Kiyingi \(n-1\) ta satrda \(u_i,v_i(1\leq u_i, v_i\leq n;u_i\neq v_i)\) juftliklar, ikki uch o'rtasida qirra mavjudligini ifodalaydi. Berilgan ma'lumotlarda daraxt berilishi kafolatlanadi.
Chiqish faylida daraxtning shunday ikki uchini chop etingki, ushbu uchlar o'rtasidagi masofada maksimal sondagi qirralar mavjud bo'lsin. Javoblar bir nechta bo'lsa istalgan javobni chop etishingiz mumkin, istalgan tartibda \((u,v)\) yoki \((v, u)\) ko'rinishida.
# | input.txt | output.txt |
---|---|---|
1 |
5 1 2 1 4 1 5 5 3 |
2 3 |