C. Тэнцвэр

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

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

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

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

Устай $n$ савтай систем өгөгдөнө. Салангид хоёр сав хоорондоо юүлэх механизмтай хоолойгоор холбогдоно. Хоёр савны аль нэг нь хоолойгоор хоёр савны хооронд бүхэл тоон утга бүхий литр ус дамжуулж болно (хоолой хоёр чиглэлд ажиллана). Хоёр савны хооронд хэд хэдэн хоолой байж болно. Бүх хоолойнуудын тоо нь $e$. Хоолой бүрийн багтаамж $v$ литр. Дамжууллын үед ямар ч савны ус $v$ литрээс их байж чадахгүй.

Савнуудад анх байсан усны хэмжээ нь $a_{i}$ ба хүсэж буй хэмжээ нь $b_{i}$ юм. Шаардагдах ажлыг хийхэд шаардлагатай юүлэлтүүдийн дарааллыг хэвлэ. Юүлэлтийн тоо нь $2*n^{2}$-аас ихгүй байх ёстой.

Оролт

Оролтын эхний мөрөнд гурван бүхэл тоон утга $n$, $v$, $e$ ($1 ≤ n ≤ 300$, $1 ≤ v ≤ 10^{9}$, $0 ≤ e ≤ 50000$) байна.

Дараагийн хоёр мөрийн мөр бүрт $n$ ширхэг бүхэл тоон утга байх ба эхний мөрөнд савнуудын усны эхлэх хэмжээ $a_{i}$ байх ба хоёр дахь мөрөнд савнуудын усны хүсэж буй $b_{i}$ хэмжээг илэрхийлнэ ($0 ≤ a_{i}, b_{i} ≤ v$).

Дараагийн $e$ мөрүүдийн мөр бүрт нэг хоолойг дараах форматаар тодорхойлно: $x$ $y$ ($1 ≤ x, y ≤ n, x ≠ y$) ба $x$ болон $y$ савнуудын хоорондох хоолой юм. Хоёр савны хооронд хэд хэдэн хоолой байж болно. Савнууд $1$-ээс $n$ хүртэл дугаарлагдана.

Гаралт

Юүлэх дараалал олдохгүй бол "$NO$" (хашилтгүйгээр) гэж хэвлэнэ.

Бусад тохиолдолд тохирох ямар ч дарааллыг дараах форматаар хэвлэ. Эхний мөрөнд юүлэлтийн нийт тоо $k$ ($k$ тоо $2*n^{2}$-с ихгүй байна) хэвлэ. Дараагийн $k$ мөрөнд юүлэлтүүдийг $x$ $y$ $d$ ($x$ савнаас $y$ савруу $d$ литрийг юүлнэ, $x$ болон $y$ ялгаатай байна) форматаар хэвлэнэ. Юүлэлт бүрийн $d$ эерэг бүхэл тоо байна.

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

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

Оролт
2 10 1
1 9
5 5
1 2
Гаралт
1
2 1 4
Оролт
2 10 0
5 2
4 2
Гаралт
NO
Оролт
2 10 0
4 2
4 2
Гаралт
0
Сэтгэгдлүүдийг ачааллаж байна...