E. Ирмэгүүдийг будах

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

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

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

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

Уг бодлогод ховор санах ойн хязгаарыг хэрэглэхийг анхаарна уу.

Танд чиглэлгүй $n$ оройнууд болон $m$ ирмэгээс тогтох граф өгөгджээ. Оройнууд нь $1$-ээс $n$ хүртэлх бүхэл тоонуудаар дугаарлагдсан, ирмэгүүд нь $1$-ээс $m$ хүртэлх бүхэл тоонуудаар дугаарлагдсан байна. Ирмэг бүр нь $1$-ээс $k$ хүртэлх бүхэл тоонуудаар дугаарлагдсан $k$ ширхэг өнгийн аль нэгээр нь будагдсан эсвэл будагдаагүй байж болно. Анхандаа ямар ч ирмэг ямар нэгэн өнгөөр будагдаагүй байх юм.

Та "$e_{i}$ ирмэгийг $c_{i}$ өнгөөр дахин будна уу" гэсэн хэлбэр бүхий асуултууд авах юм. Ямар ч үед ижил өнгийн ирмэгүүдээс тогтох граф нь заавал бипартит байх ёстой. Хэрэв дахин будалтын дараа уг нөхцөл нь зөрчигдөж байвал, уг асуултыг хэрэгжих боломжгүй гэж үзэх ба $e_{i}$ ирмэг нь өөрийн өнгөө хадгалж үлдэх юм. Бусад тохиолдолд, $e_{i}$ ирмэгийг $c_{i}$ өнгөөр дахин будах ба, уг асуултыг хэрэгжих боломжтой гэж үзнэ.

Эргэн сануулах үүднээс хэрэв уг графын оройнуудын олонлог нь 2 хэсэгт хуваагдах ба ингэснээр ирмэгээр холбогдсон ижил хэсгийн оройнууд байхгүй байвал уг графыг бипартит гэж нэрлэнэ.

Жишээлбэл, танд гурвалжин граф өгөгдсөн гэж үзье, энэ нь 3-н оройтой граф ба $(1, 2)$, $(2, 3)$ болон $(3, 1)$ гэсэн ирмэгүүдтэй байх юм. Эхний 2 ирмэг нь $1$ өнгөөр будагдсан, 3-дахь ирмэг нь $2$ өнгөөр будагдсан гэж үзье. Дараа нь "3-дахь ирмэгийг $1$ өнгөөр дахин буд" гэсэн асуулт нь буруу байх юм учир нь үүнийг хэрэгжүүлсний дараа уг граф нь $1$ гэсэн өнгийн ирмэгүүдээс тогтох ба бипартит биш байна. Өөрөөр, 2-дахь ирмэгийг $2$ өнгөөр будах нь боломжтой байна.

Та $q$ ширхэг асуулт хүлээн авна. Асуулт бүрийн хувьд, та үүнийг хэрэглээд уг асуулт нь хэрэгжих боломжтой байна гэж мэдүүлнэ эсвэл уг асуулт нь хэрэгжих боломжгүй байна гэж мэдүүлэх юм.

Оролт

Эхний мөрөнд бүхэл тоонууд $n$, $m$, $k$, $q$ ($2 ≤ n ≤ 5*10^{5}$, $1 ≤ m, q ≤ 5*10^{5}$, $1 ≤ k ≤ 50$) өгөгдөнө -- эдгээр нь оройны тоо, ирмэгийн тоо, өнгөний тоо болон асуултын тоог илэрхийлнэ.

Дараа нь графын $m$ ирмэгүүд $a_{i}$, $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$) хэлбэрээр өгөгдөнө.

Дараа нь $q$ асуултууд нь $e_{i}$, $c_{i}$ ($1 ≤ e_{i} ≤ m$, $1 ≤ c_{i} ≤ k$) хэлбэрээр өгөгдөнө.

Граф нь олон тооны ирмэгүүд болон гогцоо агуулаагүй байна.

Гаралт

Асуулт бүрийн хувьд хэрэв энэ нь хэрэгжих боломжтой бол "YES" (хашилтгүйгээр) гэж хэвлэнэ эсвэл хэрэв энэ нь ямар нэг өнгийн ирмэгүүдээс тогтох графын бипартид чанарыг зөрчиж байвал "NO" (хашилтгүйгээр) гэж хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
3 3 2 5
1 2
2 3
1 3
1 1
2 1
3 2
3 1
2 2
Гаралт
YES
YES
YES
NO
YES
Сэтгэгдлүүдийг ачааллаж байна...