CSES - Keskussolmu
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Annettuna on puu, jossa on n solmua. Tehtäväsi on etsiä puusta keskussolmu eli sellainen solmu, että kun solmusta tehdään puun juuri, jokaisessa alipuussa on enintään n/2 solmua.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: solmujen määrä. Solmut on numeroitu 1,2,\ldots,n.

Tämän jälkeen syötteessä on n-1 riviä, jotka kuvaavat verkon kaaret. Jokaisella rivillä on kaksi kokonaislukua a ja b: kaari kulkee solmujen a ja b välillä.

Tuloste

Tulosta puun keskussolmu. Jos vaihtoehtoja on useita, voit tulostaa minkä tahansa niistä. Keskussolmu on aina olemassa.

Rajat

  • 1 \le n \le 10^5

Esimerkki

Syöte:

5
1 2
2 3
3 4
3 5

Tuloste:

3