E. Хамгийн тохиромжтойгоор урсга

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

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

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

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

$1$-c $n$ хүртэл дугаарлагдсан $n$ зангилаанаас бүрдэх компьютерийн сүлжээ байна. Хос зангилаануудыг холбосон холболтууд байгаа. Хос зангилааны хувьд тэдгээрийг холбосон хэдэн ч холболт байж болох боловч өөртэйгээ холбосон холболттой нэг ч зангилаа байхгүй.

Холболт бүр хязгааргүй зурвасын өргөн (аль ч чиглэлд) дэмждэг хэдий ч шугамаар дамжиж байгаа мэдээллийн өртөг зурвасын өргөний талбайтай пропорциональ хамааралтай. Ялангуяа холболт бүр эерэг жинтэй ба холболтоор мэдээлэл дамжуулах өртөг нь зурвасын өргөнийг жин дахин үржүүлсэнтэй тэнцүү.

Сүлжээ холбогдсон (дурын зангилаанаас өөр дурын зангилааруу бүлэг холболтууд байгаа) ба түүнчлэн дурын нэг зангилаан дээр алдаа гарахад холбоотой хэвээр байгахын тулд бүтээсэн.

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

Нийт өртгийг багасгахыг хүсэж байгаа бөгөөд та сүлжээний диаграммыг зурсан тэгээд залуу мэргэжилтэнд өгсөн. Залуу мэргэжилтэн шаардсан ажлыг шийдвэрлэсэн ба таны диаграмм дээр тохиромжтой зурвасын өргөнүүдийг тэмдэглэсэн боловч үүн дээрээ кофегоо асгачихсан. Диаграммын хамаг нь уншигдахааргүй болсон (анхны диаграммын хэсгүүд болон $k$-н утгыг оролцуулаад).

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

Оролт

Оролт хоёр бүхэл тоон утга $n$ ба $m$ ($2 ≤ n ≤ 200000$; $0 ≤ m ≤ 200000$)-р эхлэх ба харгалзан сүлжээн дахь мэдэгдэж байгаа зангилаануудын болон мэдэгдэж байгаа холболтуудын тоо байна. Үүний дараа тус бүрдээ дөрвөн бүхэл тоон утгатай $m$ мөр байна: $f$, $t$, $w$, $b$ ($1 ≤ f ≤ n; 1 ≤ t ≤ n; f ≠ t; 1 ≤ w ≤ 100; 0 ≤ b ≤ 100$). Энэ нь $f$ болон $t$ зангилааны хооронд $w$ жинтэй холболт байх ба $b$ зурвасын өргөнөөр зөөж байна гэсэн үг. Зурвасын өргөний чиглэл $f$-с $t$-рүү чиглэлтэй байна.

Гаралт

Хэрвээ залуу мэргэжилтний шийдэл илэрхий хамгийн тохиромжтой биш бол "$BAD$ $x$" хэвлэх ба энд $x$ нь хамгийн тохиромжтой шийдэлтэй зөрчилдөх оролтонд өгөгдсөн хамгийн эхний холболт байна. Хэрвээ залуу мэргэжилтний шийдэл хамгийн тохиромжтой нь ба энэ шийдлийн үр ашиг хамгийн ойрын бүхэл тооруу бүхэлдэх боломжтой бол шийдлийн үр ашгийг хэвлэ, бусад тохиолдолд "UNKNOWN" гэж хэвлэ.

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

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

Оролт
4 5
1 2 1 2
1 3 4 1
2 3 2 1
2 4 4 1
3 4 1 2
Гаралт
6
Оролт
5 5
2 3 1 1
3 4 1 1
4 2 1 1
1 5 1 1
1 5 100 100
Гаралт
BAD 3
Оролт
6 4
1 3 31 41
1 5 59 26
2 6 53 58
4 6 97 93
Гаралт
UNKNOWN
Оролт
7 5
1 7 2 1
2 3 1 1
4 5 1 0
6 1 10 0
1 3 1 1
Гаралт
BAD 4

Тэмдэглэл

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

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