D. Берландын холбоот улс

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

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

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

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

Саяхан Берланд улс нь холбоот улс болох хүсэлт маш ихээр хүлээн авчээ. Хүсэлт илгээсэн хүмүүс нь уг улсыг саланги мужуудад хуваахыг хүсэж байгаа юм. Түүнчлэн тэд яг $k$ хотхон агуулсан муж байлгахыг хүсэж байв.

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

Зам тээврийн яам ялгаатай мужуудын хотхонуудыг холбох шинэ замын хуваарилалт хийсний дараа ихээхэн асуудал үүснэ хэмээн эмээж байгаа юм.

Таны даалгавар бол дараах нөхцөлүүдийг хангаж байхаар уг улсыг мужуудад хуваах юм:

  • муж болгон нь холбогдсон байна, ө.х муж болгоны хувьд уг мужийн аль ч хотхоноос аль ч бусад хотхон уруу уг мужийн замаар (уг мужийн хотхонуудыг холбох зам) дамжин очих боломжтой байна ,
  • Яг $k$ хотхон агуулсан муж байх ёстой,
  • Ялгаатай мужуудыг холбох замын тоо нь хамгийн бага байна.

Оролт

Эхний мөрөнд бүхэл тоо $n$, $k$ ($1 ≤ k ≤ n ≤ 400$) өгөгдөнө. Дараа нь $n - 1$ ширхэг мөр өгөгдөх ба мөр болгонд Берландын замыг дүрсэлнэ. Зам нь хос бүхэл тоо $x_{i}, y_{i}$ ($1 ≤ x_{i}, y_{i} ≤ n; x_{i} ≠ y_{i}$)-аар өгөгдөх ба эдгээр нь уг замаар холбогдсон хотхонуудын дугаар юм. Хотхонууд нь 1-ээс $n$ хүртэл дугаарлагдсан гэж үзнэ үү.

Гаралт

Эхний мөрөнд шаардагдсан "асуудалтай" замын хамгийн бага тоо $t$-г хэвлэнэ (ө.х ялгаатай мужуудыг холбох замын хамгийн бага тоо). Дараа нь $t$ ширхэг бүхэл тооны дараалал хэвлэнэ. Эдгээр нь таны олсон хуваалт дахь уг замуудын индексүүд байна. Замууд нь оролтод өгөгдсөн дарааллаараа 1-ээс эхлэн дугаарлагдсан байна. Хэрэв олон тооны хариулт байвал алийг нь ч хэвлэсэн болно.

Хэрэв таны хариулт нь "асуудалтай" зам огт байхгүй бол $0$ гэж хэвлэнэ үү мөн 2-р мөрийг хоосон үлдээх эсвэл юу ч хэвлэхгүй байсан болно.

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

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

Оролт
5 2
1 2
2 3
3 4
4 5
Гаралт
1
2
Оролт
5 3
1 2
1 3
1 4
1 5
Гаралт
2
3 4
Оролт
1 1
Гаралт
0

Сэтгэгдлүүдийг ачааллаж байна...