D. Тэнэгүүд ба Замууд

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

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

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

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

Та газарзүйн хичээлүүд дээрээ Фүүллэндийн тухай сонссон байх. Ялангуяа энэ улсын засаг захиргааны бүтэц олон зууны турш нэг хэвээрээ байгаа гэдгийг. Энэ улс $n$ хотоос тогтох ба зарим хотууд хоорондоо хос чиглэлтэй замаар холбогдсон, зам бүр өөрийн $l_{i}$ уртаараа тодорхойлогдоно.

Тэнэгүүд өөрийн нутагтаа баяртайгаар амьдардаг боловч саяхны шинэчлэлээр хаан солигдсон. Одоогийн хаан бол Баавгай Васили. Васили улсынхаа хотуудыг бүс нутагруу хуваасан ба нэг бүс нутгийн ямар ч хоёр хот хоорондоо замуудын дагуу байрлах замтай байх бол ялгаатай бүс нутгийн дурын хоёр хот хоорондоо ийм жимгүй байна. Ингээд Васили замын сүлжээг сайжруулж, улсын хэмжээнд яг $p$ ширхэг шинэ зам барихаар шийдсэн.

  1. Бид хоорондоо шинэ замаар холбогдох ялгаатай хоёр хот $u$, $v$-г сонгоно (энд эдгээр хотуудын хооронд аль хэдийн замтай байх боломжтой).
  2. Бид шинэ замын уртыг тодорхойлно: хэрвээ $u$, $v$ хотууд нь ялгаатай бүс нутагт хамаарч байвал замын урт нь $min(10^{9}, S + 1)$ байна (энд $S$ нь холбогдсон бүс нутгууд дахь бүх замуудын уртуудын нийлбэр), бусад тохиолдолд бид уртыг $1000$ гэж авч үзнэ.
  3. Бид сонгогдсон хотуудын хооронд тодорхойлсон урттай замыг барина. Хэрвээ зам маань ялгаатай хоёр бүс нутгийг холбож байвал замыг барьсаны дараа эдгээр бүс нутгууд нь нэг бүс нутаг болж нэгдэнэ.

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

Оролт

Эхний мөрөнд дөрвөн бүхэл тоо $n$ ($1 ≤ n ≤ 10^{5}$), $m$ ($0 ≤ m ≤ 10^{5}$), $p$ ($0 ≤ p ≤ 10^{5}$), $q$ ($1 ≤ q ≤ n$) байх буюу Фүүллэнд дахь хотуудын тоо, одоо байгаа замуудын тоо, барихаар төлөвлөсөн замуудын тоо болон шаардлагатай бүс нутгийн тоо байна.

Дараагийн $m$ мөрөнд замын шинэчлэл хийгдэх үед оршин буй замуудыг тодорхойлно. Эдгээр мөр тус бүрт $x_{i}$, $y_{i}$, $l_{i}$ гурван бүхэл тоо байх ба $x_{i}$, $y_{i}$ нь энэ замаар холбогдсон хотуудын дугаар байна ($1 ≤ x_{i}, y_{i} ≤ n, x_{i} ≠ y_{i}$), харин $l_{i}$ нь уг замын урт байна ($1 ≤ l_{i} ≤ 10^{9})$. Аль нэг хоёр хот хоорондоо нэгээс олон замаар холбогдсон байж болно.

Гаралт

Хэрвээ замуудыг байгуулах шаардлагатай арга нь боломжгүй бол "$NO$" (хашилтгүйгээр) гэсэн дан тэмдэгт мөрийг хэвлэ. Бусад тохиолдолд эхний мөрөнд "$YES$" (хашилтгүйгээр) хэвлэнэ, дараагийн $p$ мөрөнд зам байгуулалтын төлөвлөгөөг хэвлэнэ. Төлөвлөгөөний мөр бүр уг замаар холбогдсон хоёр хотын дугаарыг илэрхийлэх ялгаатай хоёр бүхэл тоог агуулсан байх ёстой. Замуудыг баригдах шаардлагатай дарааллаар нь төлөвлөгөөнд хэвлэнэ үү. Хэрвээ хэд хэдэн тохиромжтой шийдэл байвал та алийг нь ч хэвлэж болно.

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

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

Оролт
9 6 2 2
1 2 2
3 2 1
4 6 20
1 3 8
7 8 3
5 7 2
Гаралт
YES
9 5
1 9
Оролт
2 0 1 2
Гаралт
NO
Оролт
2 0 0 2
Гаралт
YES

Тэмдэглэл

Эхний жишээг авч үзье. Фүүллэндийг шинэчлэхээс өмнө дөрвөн бүс нутагтай байна. Эхний бүс нутагт $1$, $2$, $3$ хотууд, хоёрдугаар бүс нутагт $4$ ба $6$ хотууд, гуравдугаар бүс нутагт $5$, $7$, $8$ хотууд, дөрөвдүгээр бүс нутагт $9$ дугаартай хот байна. Эдгээр бүс нутгууд дахь замуудын нийт урт нь харгалзан $11$, $20$, $5$, $0$ байна. Төлөвлөгөөний дагуу бид эхлээд $5$ болон $9$ дугаартай хотуудын хооронд $6$ урттай зам барина. Тэгээд $1$ болон $9$ дугаартай хотуудын хооронд $23$ урттай зам барина. Ингээд барьсан замуудын нийт урт $29$ байна.

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