D. Триландын нийслэлийг сонгох

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Трийланд улс нийт $n$ хоттой. Тэдгээрийн зарим нь хоорондоо хос чиглэлт замаар холбогдсон байна. Улс нийт $n-1$ хоттой. Хэрвээ бид замуудын чиглэлд ач холбогдол өгөхгүй бол аль ч хотоос аль ч хотруу замуудаар дамжин очих боломжтой байдаг.

Саяхан хөгшдийн зөвлөл улсын шинэ нийслэлийг сонгохоор болжээ. Мэдээж шинэ нийслэл аль нэг хот байх ёстой. Зөвлөлийнхөн нийслэлдээ уулзаад, тэндээсээ бүгд өөрсдийн хотруу буцах төлөвлөгөөтэй байгаа (хэн ч хотоосоо нийслэлрүү эргэн очих тухай бодоогүй). Хэрвээ бид $a$ хотыг нийслэлээр сонговол нэг хотоос дайрах бүх зам $a$-руу чиглэлсэн үед бид $a$-д очиж чадна. Үүний тулд бид зарим замын чиглэлийг өөрчлөх боломжтой.

Хамгийн цөөн замын чиглэлийг солиод шаардлага хангах нийслэлийг сонгож байхаар хөгшдөд нийслэлийг сонгож өгнө үү.

Оролт

Эхний мөрөнд Трийландын хотын тоо $n$ ($2 ≤ n ≤ 2·10^5$) өгөгдөнө. Дараагийн $n-1$ мөр бүрт замуудын мэдээлэл өгөгдөнө. $i$ замд холбогдсон хотууд нь $s_i$, $t_i$ ($1 ≤ s_i, t_i ≤ n$; $s_i ≠ t_i$) хэлбэртэй өгөгдөнө. Энд $s_i$-с $t_i$-рүү чиглэсэн зам байгаа гэсэн үг. Та хотуудыг $1$-с $n$ хүртэл дугаарлагдсан гэж үзээрэй.

Гаралт

Эхний мөрөнд нийслэл хотыг сонгоход хэдэн замын чиглэл өөрчлөх хэрэгтэйг хэвлэ. Дараагийн мөрөнд сонгогдох боломжтой хотуудын дугаарыг өсөх эрэмбэтэйгээр хэвлэнэ үү.

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
3
2 1
2 3
Гаралт
0
2 
Оролт
4
1 4
2 4
3 4
Гаралт
2
1 2 3 
Сэтгэгдлүүдийг ачааллаж байна...