D. FreeDiv тоглоом

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

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

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

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

Вася "FreeDiv" тоглоомоор тоглодог. Энэ тоглоомонд тэр $n$ хот ба тэдгээрийг хооронд нь холбодог хоёр чиглэлт $m$ замыг удирдан зохион байгуулдаг. Харамсалтай нь эдгээр замуудыг ашиглан хот болгоноос дурын өөр хотод очих боломжгүй байдаг.

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

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

Гэхдээ бас нэг асуудал гарсан нь муж бүрд хамгийн ихдээ л $k$ ширхэг хонгил байлгах боломжтой байв. Учир нь үүнээс олон бол, нэг муж л эзлэгдэхэд бусад мужуудынхаа аюулгүй байдалд асуудал учруулах байлаа.

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

Оролт

Эхний мөрөнд $n$, $m$, $k$ ($1 ≤ n, k ≤ 10^{6}, 0 ≤ m ≤ 10^{6}$) гурван бүхэл тоо байрлана. Дараагийн $m$ мөрөнд мөр бүрт хоёр бүхэл тоо болох хоорондоо холбогдсон хотуудын дугаар байна. Хот өөртөөгөө холбогдсон зам байхгүй ба хоёр хотын хооронд хамгийн ихдээ нэг л зам байна.

Гаралт

Нэмж барих замын боломжит хамгийн бага утга.

Орчуулсан: gmunkhbaatarmn

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

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

Тэмдэглэл

Эхний жишээн дээр зөвхөн ганц мужтай ба нэмж ямар нэгэн зам юм уу хонгил барих шаардлагагүй.

Хоёр дахь жишээн дээр хоёр муж өгөгдсөн байна. $1$ ба $3$ дугаартай хотуудын хооронд хонгил барихад болно.

Гурав дахь жишээн дээр хамгийн багадаа нэг нэмэлт зам барих шаардлагатай. Жишээ нь, $1$ ба $2$ дугаартай хотуудын хооронд нэмэлт зам бариад $1$ ба $3$, $2$ ба $4$ хотуудыг хонгилоор холбоход болно.

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