Գտնել ծառի կենտրոնը
Տրված է
n քաղաք, որոնք միմյանց միացած են n-1 ճանապարհով։ Բոլոր քաղաքները փոխադարձաբար հասանելի են (գուցե այլ քաղաքների միջոցով)։ Ցանկանում եք մայրաքաղաքը տեղակայել հնարավոր ամենալավ վայրում։Որոշում եք, որ «լավագույն» վայրն այն է, որտեղ սահմանային քաղաքներից (այսինքն, այն քաղաքներ, որոնք միայն մեկ այլ քաղաքի հետ են կապված) առավելագույն հեռավորությունը հնարավորինս փոքր է։ Ո՞ր քաղաքներն են ամենահարմար թեկնածուները մայրաքաղաք լինելու համար։
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
v (1 ≤ v ≤ 100000)։Հաջորդ
v-1 տողերում բերված են զույգ ամբողջ թվեր v1 և v2 (1 ≤ v1, v2 ≤ v), որոնք ցույց են տալիս, որ գագաթ v1-ը կապված է գագաթ v2-ի հետ, և ընդհակառակը։Ելք
Ծրագիրը պետք է տպի մայրաքաղաքի լավագույն թեկնածուներին աճող կարգով։
Օրինակ
Մուտք | Ելք |
4
1 2
2 3
3 4 | 2 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB