C. ХЭХ 2

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

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

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

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

'Боолеан илэрхийлэлд хэрвээ томьёо нь хувьсагчуудаас бүрдсэн нэгдлүүдийн холбоос хэлбэртэй байвал холбоост энгийн хэлбэртэй (ХЭХ) эсвэл нийлмэл энгийн хэлбэртэй байна' (https://en.wikipedia.org/wiki/Conjunctive_normal_form хаягаас иш татав)

Өөрөөр ХЭХ нь хэлбэрийн томьёо юм, энд $\&$ нь логик "AND" (холбоос) үйлдлийг илэрхийлэх бол нь логик "OR" (салгалт) үйлдлийг илэрхийлэх ба $v_{ij}$-ууд нь боолеан хувьсагчууд эсвэл тэдний үгүйсгэл байна. Хаалтан дотор байгаа илэрхийлэл бүрийг нэгдэл гэх ба $v_{ij}$ бүрийг хувьсагч гэнэ.

Танд $x_{1}, ..., x_{m}$ хувьсагчууд болон тэдний үгүйсгэлийг агуулсан ХЭХ өгөгдсөн. Бид хувьсагч бүр хамгийн ихдээ хоёр нэгдэлд (нийтдээ үгүйсгэлтэйгээр, үгүйсгэлгүйгээр) агуулагдана гэдгийг мэднэ. Таны ажил бол уг ХЭХ нь нийцэхүйц эсэхийг тодорхойлох буюу ХЭХ нь үнэн байх хувьсагчуудын утгууд байгаа эсэхийг тодорхойлох юм. Хэрвээ ХЭХ нийцэхүйц байвал ХЭХ нийцэхүйц байгаа хувьсагчуудын утгыг тодорхойлох хэрэгтэй.

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

Оролт

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

Дараагийн $n$ мөрөнд нэгдэл бүрийн тайлбар байна. $i$-р мөрөнд эхлээд эхний тоо $k_{i}$ ($k_{i} ≥ 1$) байх буюу $i$-р нэгдэл дахь хувьсагчуудын тоо байна. Тэгээд зайгаар тусгаарлагдсан хувьсагчууд $v_{ij}$ ($1 ≤ |v_{ij}| ≤ m$) байна. $v_{ij}$-тэй харгалзах хувьсагч $v_{ij}$ нь үгүйсгэлтэй бол $x_{|v_{ij}|}$ байна эсвэл бусад тохиолдолд үгүйсгэлгүй байна.

Гаралт

Хэрвээ ХЭХ нь нийцэхүйц биш бол нэг мөрөнд "$NO$" (хашилтгүйгээр) гэж хэвлэ, бусад тохиолдолд хоёр тэмдэгт мөр хэвлэ: "$YES$" (хашилтгүйгээр), тэгээд тэг эсвэл нэгээс бүрдсэн $m$ тэмдэгт мөр. Энд тэг болон нэгүүд нь $x_{1}$-с $x_{m}$ дараалалтай даалгаварыг нийцүүлж буй хувьсагчуудын утга юм.

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

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

Оролт
2 2
2 1 -2
2 2 -1
Гаралт
YES
11
Оролт
4 3
1 1
1 2
3 -1 -2 3
1 -3
Гаралт
NO
Оролт
5 6
2 1 2
3 1 -2 3
4 -3 5 4 6
2 -6 -4
1 5
Гаралт
YES
100010

Тэмдэглэл

Эхний жишээн дээр томьёо нь . Боломжит хариултуудын нэг нь $x_{1} = TRUE, x_{2} = TRUE$ байна.

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