D. Дуфф Мафид

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

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

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

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

Дуфф бол өөрийн улс Андарз Гу-н Мафын толгойлогчдын нэг. Андарз Гу нь $m$ хос чиглэлтэй замаар ($1$-c $m$ хүртэл дугаарлагдсан) холбогдсон $n$ хоттой ($1$-c $n$ хүртэл дугаарлагдсан).

Зам бүр устах хугацаа болон өнгөтэй. $i$-р зам $v_{i}$ ба $u_{i}$ хотуудыг холбох ба $c_{i}$ өнгөтэй мөн устах хугацаа нь $t_{i}$ байна.

Мафи Андарз Гу дахь тааралтуудыг устгахыг хүссэн. Тааралт гэдэг нь дэд бүрдэл дэхь ямар ч хоёр зам ижил төгсгөлийн цэггүй байх замуудын дэд бүрдлийг хэлнэ. Тэд эдгээр замуудыг параллелаар устгаж болох буюу нийт устгах хугацаа нь бүх сонгогдсон замуудын устах хугацаануудын хамгийн их нь байна.

Тэд хангагдах хоёр нөхцөл хүсч байгаа:

  1. Үлдсэн замууд зохистой өнгөтэй.
  2. Уг тааралтыг устгах хугацааг хамгийн бага байлгах.

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

Мафид програмчлагч байхгүй. Энэ нь Дуфф таны тусламжийг хүссэн шалтгаан. Түүнд эдгээр нөхцөлүүд (эсвэл боломжгүй гэх төлөв) хангагдахын тулд аль тааралтыг устгахыг тодорхойлж өгч туслана уу.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($2 ≤ n ≤ 5 × 10^{4}$ and $1 ≤ m ≤ 5 × 10^{4}$) байх ба улсын хотууд болон замуудын тоо байна.

Дараагийн $m$ мөрөнд замууд байна. Эдгээрийн $i - p$ мөрөнд дөрвөн бүхэл тоон утга $v_{i}, u_{i}, c_{i}$ ба $t_{i}$ ($1 ≤ i ≤ m$ бүрийн хувьд $1 ≤ v_{i}, u_{i} ≤ n$, $v_{i} ≠ u_{i}$ ба $1 ≤ c_{i}, t_{i} ≤ 10^{9}$).

Гаралт

Гаралтын эхний мөрөнд хэрвээ эхний нөхцөл биелэж байвал "$Yes$"-г (хашилтгүйгээр) хэвлэх ба бусад тохиолдолд "$No$" (хашилтгүйгээр) хэвлэ.

Хэрвээ энэ боломжтой бол та хоёр дахь мөрөнд хоёр бүхэл тоон утга $t$ ба $k$-г хэвлэх ба хамгийн бага устгах хугацаа ба тааралтанд байгаа замуудын тоо () байна.

Гурав дахь мөрөнд зайгаар тусгаарлагдсан $k$ ялгаатай бүхэл тоон утгыг хэвлэх ба тааралтанд байгаа замуудын дугаарыг дурын дарааллаар хэвлэнэ. Замууд оролтонд өгөгдсөн дарааллаараа нэгээс эхлэн дугаарлагдана.

Хэрвээ хэд хэдэн шийдэл байвал алийг нь ч хэвлэж болно.

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

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

Оролт
5 7
2 1 3 7
3 1 1 6
5 4 1 8
4 5 1 1
3 2 2 3
4 5 2 5
2 3 2 4
Гаралт
Yes
3 2
4 5
Оролт
3 5
3 2 1 3
1 3 1 1
3 2 1 4
1 3 2 2
1 3 2 10
Гаралт
No

Тэмдэглэл

Эхний жишээн дээрх Андарк Гу-н зураг дараах байдлаар харагдана:

Шийдэл нь Х-лэсэн замуудыг устгах байна.

Хоёр дахь жишээн дээрх Андарк Гу-н зураг дараах байдлаар харагдана:

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