Masala #A3OIKNFFXV

Xotira 32 MB Vaqt 2000 ms
14

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?


Kiruvchi ma'lumotlar:

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.


Chiquvchi ma'lumotlar:

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.


Misollar
# input.txt output.txt
1
5
1 2
1 4
1 5
5 3
2 3