Zadanie

Egreše

Počet bodov: 35

Ríbezľa egrešová alebo egreš obyčajný je druh kra z čeľade egrešovité. Pre nás informatikov, je to strom. Vrcholy každého stromu si môžeme očíslovať. Vrchol je každé miesto, kde sa náš egreš ohýba, rozkonáruje, alebo kde nejaký konár končí.

Informatické mravce si náš Egreš takto očíslovali, a chceli by vedieť, kde si majú postaviť základňu. Základňa musí byť na takom vrchole, aby sa do každého iného dalo dostať cez najmenší možný počet iných vrcholov. Teda keď si mravce vyberajú spomedzi dvoch vzcholov, tak sa pozrú, cez kolko vrcholov sa z neho ide na ten najvzdialenejší, a zoberú si ten, pre ktorý je to menej.

Nájdite niektorý taký vrchol, že mravčeky žiadny lepší nenájdu.

Vstup a výstup

V prvom riadku vstupu je číslo \(n\) - počet vrcholov.

Nasleduje \(n-1\) riadkov, každý obsahuje dve medzerou oddelené čísla \(a_i\) \(b_i\) – medzi vrcholmi \(a_i\) a \(b_i\) vedie konár (\(1\leq a_i, b_i\leq n\)).

V jednotlivích sadách je \(n\) najviac postupne \(100\), \(1\,000\), \(50\,000\), \(200\,000\)

Príklady

Input:

3
1 2
3 2

Output:

2

Z vrcholu dva sa dá pramo dostať aj do \(1\) aj do \(3\).

Input:

4
1 2
2 4
4 3

Output:

2

\(4\) by bola rovnako správna odpoveď, nakoľko z oboch je najvzdialenejší vrchol rovnako ďaleko.