D. Супер М

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

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

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

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

Мангас Ари бол энгийн биш мангас. Тэр Байтфорсесийн супер баатар болох Супер М-н нуугдсан хэлбэр. Байтфорсес бол $n - 1$ хос чиглэлтэй замуудаар холбогдсон $n$ хотоос бүрдэх улс юм. Зам бүр ялгаатай хоёр хотыг холбох ба замын систем нь бүхэлдээ дурын хотоос өөр дурын хотруу зөвхөн өгөгдсөн замуудаар л хүрэх боломжтой байхаар бүтээгдсэн. Энд хүмүүсийн дайралтад өртсөн $m$ хот байна. Иймээс Ари... Супер М-ийг халдлагад өртсөн хотуудруу түргэн очуулж муу хүмүүсийг айлгая гэж бодсон. Супер М нэг хотоос нөгөөд очихдоо зөвхөн өгөгдсөн замуудаар л дайрч явна. Мөн түүнчлэн нэг замаар дайрч өнгөрөхдөө тэр яг нэг крон зарцуулах буюу крон гэдэг нь Байтфорсесд хэрэглэгддэг хугацааны нэгж.

Гэсэн хэдий ч Супер М одоо Байтфорсесд алга байгаа ба Кодфорсес улсын ойролцоо байрласан кэмпд сургалтанд сургуулилж байгаа. Аз болж Кодфорсесд түүнийг Кодфорсесоос Байтфорсесийн дурын хотруу хоромхон зуурт тээвэрлэх онцгой төхөөрөмж байна. Буцах зам маш урт ба уг бодлогын зорилго нь энэ төхөөрөмжийг ганц л удаа ашиглаж болно.

Та Супер М-д тэр ажлаа хамгийн бага хугацаанд (кроноор хэмжигдэнэ) хийж чадахын тулд хамгийн эхэнд аль хотод очих ёстойг тооцоолж туслах хэрэгтэй. Мөн түүнийг энэ цагаар хангах ба ингэснээр тэр Кодфорсесруу буцах замаа төлөвлөж чадна.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($1 ≤ m ≤ n ≤ 123456$) байх ба харгалзан Байтфорсесийн хотуудын тоо ба халдлагад өртсөн хотуудын тоо байна.

Дараагийн $n - 1$ мөрөнд замын системийг тодорхойлно. Мөр бүр хоёр хотын дугаар $u_{i}$ ба $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$) агуулах ба $i$-р замаар холбогдож байгаа хотуудын дугаар.

Сүүлийн мөрөнд $m$ ширхэг ялгаатай бүхэл тоон утгууд байх ба халдлагад өртсөн хотуудын дугаар байна. Эдгээр тоонууд ямар ч тусгай дарааллаар өгөгдөхгүй.

Гаралт

Эхлээд Супер М-н төхөөрөмжөөр очих хотын дугаарыг хэвлэнэ. Хэрэв олон боломжит хамгийн тохиромжтой хариултууд байвал хамгийн бага хотын дугаарыг хэвлэ.

Тэгээд халдлагад өртсөн хотуудад байгаа бүх хүмүүсийг айлгахад шаардлагатай цагийн боломжит хамгийн бага утгыг хэвлэ, Кроноор хэмжинэ.

Зөв хариулт үргэлж давтагдашгүй байна.

Орчуулсан: Г.Мэндбаяр

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

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

Тэмдэглэл

Эхний жишээн дээр Супер М ажлаа $3$ кронд дуусгах хоёр боломж байна. Эдгээр нь:

ба .

Гэсэн хэдий ч та бага дугаартай хотоос эхэлж байгаа эхнийхийг нь сонгох ёстой.

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