C. Дэлхийг эзэгнэгч ах дүүс

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

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

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

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

Та дэлхийг эзэгнэхийг мөрөөддөг ах дүү 2-ын талаар сонссон байх. Тэдгээрийн өмнөх бүх төлөвлөгөө нь бүтэлгүйтсэн учраас энэ удаад тэд бие биетэйгээ хамтран дэлхийг эзэгнэхээр шийджээ.

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

Ах дүү тус бүр нь ямар нэгэн улсад өөрийн ноёрхлыг тогтоохыг хүсэх ба тэгсэн тохиолдолд тэд чиглэлтэй замуудаар дамжин өөрийн улсаас эхлэн явсаар хүрч болох улсуудыг удирдах боломжтой юм.

Хэрэв хамгийн ихдээ 2 улсыг ах дүүс сонгох ба (өөрөөр хэлбэл эдгээр улсуудад өөрсдийн ноёрхлоо тогтооно) ингэснээр тэдгээрийн ядаж нэг нь бусад бүх улсуудыг удирдлагадаа авч чадаж байвал ах дүүс дэлхийг эзэгнэж байна гэж үзнэ. Үүнийг боломжтой болгохын тулд ах дүүс хамгийн бага тооны замын чиглэлийг солих юм. Таны даалгавар бол уг хамгийн бага замын тоог олох юм.

Оролт

Эхний мөрөнд бүхэл тоо $n$ $(1 ≤ n ≤ 3000)$ өгөгдөнө. Дараагийн $n - 1$ мөрийн мөр болгонд зайгаар тусгаарлагдсан 2 бүхэл тоо $a_{i}$ болон $b_{i}$ $(1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i})$ өгөгдөх ба эдгээр нь $a_{i}$ улсаас $b_{i}$ улс хүртэл зам байгааг илэрхийлнэ.

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

Гаралт

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

Орчуулсан: Баатархүү

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

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