B. Орлуулах процессууд

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

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

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

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

Нэгэн томоохон программ хангамжийн компани өөрсдийн олон нийтийн сүлжээг хөгжүүлдэг билээ. Хэрэглэгчид ихэвчлэн өөрсдийн амралт, гол спортын өдөрлөгүүд болон бусад тэмдэглэлт өдрүүдийн турш сүлжээнд нэвтэрдгийг шинжээчид өөрсдийн дэд бүтцэд илүү их ачаалал ирдгээр нь дүгнэжээ.

Энэхүү даалгаврын хэсэгт бид олон нийтийн сүлжээг $n$ ширхэг сервер дээрх $4n$ процесс гэж тодорхойльё. Бүх серверүүд нь $1$ GB = $1024$ MB $^{(1)}$ RAM багтаамжтай. Процесс бүр сервертээ 100 MB RAM ашиглаж ажилладаг. Мөн серверийн ачааллах хэрэгцээ нь $100$-с илүү мегавайттай RAM шаардагддаг. Түүнчлэн, сервер бүр $9$ ширхэг процесс ажиллуулах багтаамжтай.

Одоо $n$ ширхэг серверүүд бүр яг $4$ процессийг ачаалж байна. Гэсэн ч, ачааллын өндөр түвшинд зарим тохиолдолд хуучин $4n$ процессуудын оронд шинэ $8n$ процессоор шинэчлэх шаардлагатай байдаг. Энгийнээр орлуулах дүрэм гэх бөгөөд $1$ процессийг $2$ ширхэг болгон серверүүдэд тараадаг. $i$ ($1 ≤ i ≤ 4n$) дэхь процессийн хувьд $a_{i} -> (b_{i}, c_{i})$ томьёоны дагуу орлуулна. Энд $a_{i}$, $b_{i}$ болон $c_{i}$ ($1 ≤ a_{i}, b_{i}, c_{i} ≤ n$) серверийн дугаарууд. Энэ нь $a_{i}$ сервер дээр ачааллаж байгаа хуучин процессын оронд $b_{i}$ болон $c_{i}$ серверүүд дээр $2$ шинэ процессын хуудбарууд гарч ирнэ гэсэн үг. Энэ 2 орлуулагдсан процессууд нь ижил сервер дээр (i.e., $b_{i}$, $c_{i}$ 2 нь хоорондоо тэнцүү байж болно) эсвэл бүр анхны сервертэйгээ ч адилхан байж болох юм (i.e. $a_{i}$ нь $b_{i}$ юмуу $c_{i}$-тэй тэнцэж болно). Энэхүү орлуулалт $a_{i} -> (b_{i}, c_{i})$-ын процесс нь дараах байдлаар хийгдэнэ. Эхлээд $a_{i}$ серверээс $i$ дэхь процесс устаж, дараа нь $b_{i}$ дээр процесс бий болж, тэгээд $c_{i}$ дээр процесс бий болно.

Танд $4n$ ширхэг дүрэм өгөгдөнө. Эдгээр дүрмүүд нь анхны $4n$ ширхэг процессийг устгаж, шинэ $8n$ ширхэг процесс үүсгэнэ. Үүний дараа $n$ ширхэг сервер болгон дээр $8$-н ширхэг сервер байх болно. Гэсэн хэдий ч, энэ дүрмүүд зөвхөн дэс дараатай уншигддаг бөгөөд түүнчлэн серверүүдийн RAM-н хэмжээ эдгээр процесс орлуулалтын хязгаарлалт болж өгдөг.

Эдгээр дүрмүүдийн дагуу сервер болгон дээр хамгийн ихдээ $9$-н ширхэг процесс байхаар бүх $4n$ дүрмүүдийн дарааллыг хэлнэ үү. Харин ийм дараалал байх боломжгүй бол боломжгүйг хэвлэнэ үү.

Оролт

Эхний мөрөнд олон нийтийн сүлжээнд байгаа серверүүдийн тоо болох нэг бүхэл тоо $n$ ($1 ≤ n ≤ 30 000$) өгөгдөнө.

Дараагийн $4n$ ширхэг мөрөнд орлуулах дүрмүүд өгөгдөнө. $i$ дэхь мөрөнд $a_{i} -> (b_{i}, c_{i})$ дүрмийг тодорхойлж буй $a_{i}, b_{i}, c_{i}$ ($1 ≤ a_{i}, b_{i}, c_{i} ≤ n$) өгөгдөнө.

Энд нийт $4n$ ширхэг дүрэм байх нь баталгаатай бөгөөд бүх $b_{i}$, $c_{i}$-г нийлүүлж тоолвол $8n$ ширхэг процесс үүсэх ёстой.

Гаралт

Хэрвээ шаардагдаж буй дүрмийн дараалал олдох боломжгүй бол $NO$ гэж хэвлэнэ үү.

Харин олдож байвал эхний мөрөнд $YES$ гэж хэвлэнэ үү. Тэгээд 2 дахь мөрөнд $1$-ээс $4n$ хүртэл $4n$ ширхэг тоог хэвлэнэ үү. Эдгээр нь дүрмүүдийн орлуулах дараалал юм (Энэ дараалалд нэг тоо зөвхөн нэг л удаа орсон байх ёстой).

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

Орчуулсан: Энхлут

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

Оролт
2
1 2 2
1 2 2
1 2 2
1 2 2
2 1 1
2 1 1
2 1 1
2 1 1
Гаралт
YES
1 2 5 6 3 7 4 8
Оролт
3
1 2 3
1 1 1
1 1 1
1 1 1
2 1 3
2 2 2
2 2 2
2 2 2
3 1 2
3 3 3
3 3 3
3 3 3
Гаралт
YES
2 3 4 6 7 8 10 11 12 1 5 9

Тэмдэглэл

Нарийвчлал сайтай байхын тулд сервер $1$ GiB = $1024$ MiB санах ойтой, процесс болгон $100$ MiB RAM шаарддаг. Энд гибибайт (GiB) нь $2^{30}$ байтын хэмжээтэй RAM, харин мэбибайт (MiB) нь $2^{20}$ байтын хэмжээтэй RAM юм.

Эхний жишээнд сүлжээ $2$ сервертэй. Сервер болгон $4$-н процесстэй. Дүрмүүдийн дагуу процесс болгон устаж оронд нь $2$ ширхэг процесс бий болно. Боломжтой хариултуудын нэг нь өгөгджээ: $1$ болон $2$ дугаар дүрмийг хэрэгжүүлсний дараа эхний сервер $2$ хуучин процесстэй, харин сервер хоёр дахь сервер $8$-н процесстэй болно ($4$-н шинэ, $4$-н хуучин). Дараа нь $5$, $6$ дүрмүүдийг хэрэгжүүлсний дараа сервер болгон $6$ ширхэг процесстэй болно. Тэгээд $3$, $7$ дүрмүүдийг хэрэгжүүлсний дараа сервер болгон $7$ ширхэг процесстэй болно. Үүний дараа $4$, $8$ дүрмүүдийг хэрэгжүүлсний дараа сервер болгон $8$-н ширхэг процесстэй болно. Аль ч үед сервер болгоны процессийн тоо $9$-ийг хэтрэхгүй болно.

2 дахь жишээнд сүлжээнд нийт гурван сервер байна. Сервер болгон дахь $4$-н процессийн $3$ нь тухайн сервер дээрээ $2$ ширхэг болон орлуулагдаж байна. Харин үлдсэн нэг процесс нь орлуулагдахдаа үлдсэн 2 сервер дээр нэг нэгээрээ орлуулагдаж байна. Ингээд дүрмүүдийг эхлээд $2, 3, 4, 6, 7, 8, 10, 11, 12$, дараа нь $1, 5, 9$ дараалалтайгаар хэрэгжүүлэхэд сервер болгон $8$ ширхэг процесстэй болох ба аль ч үед сервер болгоны процессийн тоо $9$-ийг хэтрэхгүй.

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