D. Вант Улсаа хуваах II

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

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

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

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

Эрт цагт нэгэн агуу вант улс байсан ба энэ улсыг Агуу Аря Пари хоёр захирдаг байсан. Аря Пари хоёр өөр өөр тоонуудад дуртай байсан учир агуу вант улсаа хоорондоо хуваахаар шийдсэн.

Агуу вант улсад $1$-c $n$ хүртэл дугаарлагдсан $n$ хот байх ба тэдгээрийг холбосон $m$ хос чиглэлтэй зам байна, замууд $1$-c $m$ хүртэл дугаарлагдана. $i$-р замын урт нь $w_{i}$ байна. Агуу Аря Пари хоёр замуудын зарим угтвар ($x$ тооноос бага дугаартай бүх зам) болон дагаваруудыг ($x$ тооноос их дугаартай бүх зам) сүйтгэх тал дээр хэлэлцсэн ба энд зөвхөн $l, l + 1, ..., r - 1$ ба $r$ дугаартай замууд л үлдэнэ.

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

Түүхчид агуу вант улсын газрын зургийг олсон ба тэдэнд агуу удирдагчдын сонгосон $l$ ба $r$-н талаар $q$ таамаглал байна. Эдгээр мэдээлэл өгөгдсөн бол $l_{i}$ ба $r_{i}$ таамаглал бүрийн хувьд вант улсын хэсгийн хатуу чанарыг илтгэх боломжит хамгийн бага тоог хэвлэ.

Оролт

Оролтын эхний мөрөнд гурван бүхэл тоон утга $n$, $m$ ба $q$ ($1 ≤ n, q ≤ 1000$, ) байх ба харгалзан вант улсын хотууд болон замуудын тоо ба таамаглалуудын тоо юм.

Дараагийн $m$ ширхэг мөрний $i$-р мөрөнд гурван бүхэл тоон утга $u_{i}$, $v_{i}$ and $w_{i}$ ($1  ≤  u_{i},  v_{i}  ≤  n, 0 ≤ w_{i} ≤ 10^{9}$) байх буюу $i$-р замаар холбогдсон хотуудын дугаар $u_{i}$, $v_{i}$ ба уг замын урт $w_{i}$ юм. Ямар ч зам нэг хотыг өөртэй нь холбохгүй ба ямар ч хоёр хот хоорондоо нэгээс олон замаар холбогдохгүй.

Дараагийн $q$ мөр бүрт хос бүхэл тоо $l_{i}$ ба $r_{i}$ ($1  ≤ l_{i} ≤ r_{i} ≤ m$) байх буюу түүхчдийн вант улсад үлдсэн замуудын тухай гаргасан таамаглалууд юм.

Гаралт

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

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

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

Оролт
5 6 5
5 4 86
5 1 0
1 3 38
2 1 33
2 4 28
2 3 40
3 5
2 6
1 3
2 3
1 6
Гаралт
-1
33
-1
-1
33
Сэтгэгдлүүдийг ачааллаж байна...