Бяцхан Артем нь ухаалаг ирээдүй программист юм. Тэрээр маш олон ялгаатай хүнд алгоритмуудыг мэддэг бөгөөд саяхан тэрээр 2-SAT гэх нэгэн алгоримтыг маш сайн сурчээ.

Компьютерын шинжлэх ухаанд 2-satisfiability (2-SAT гэж товчилж бичдэг) гэдэг нь тусгаарлалтуудын (логикийн OR үйлдэл) холбоосууд (логикийн AND үйлдэл) нь ямар нэгэн хариутай эсэхийг тодорхойлох нэгэн бодлогын онцгой тохиолдол бөгөөд үүнд бүх тусгаарлалтууд нь 2-оос ихгүй аргументээс (хувьсагчид) тогтсон байх юм. Уг бодлогод зориулан бид зөвхөн тусгаарлалт болгон нь яг 2 ширхэг аргументээс тогтох 2-SAT томьёонуудыг авч үзнэ.

Дараах 2-SAT бодлогыг жишээ болгон авч үзье: . 2-SAT томьёон дотор үгүйсгэлүүд байж болохыг анхаарна уу. Жишээлбэл уг томьёо дотор $x_{1}$ болон $x_{4}$-ын үгүйсгэлүүд байна.

Одоо Артем 2-SAT хэлбэртэй аль болох олон бодлогууд бодохыг хичээж байгаа юм. Тэрээр нэгэн сонирхолтой 2-SAT бодлого олсон бөгөөд хараахан өөрөө бодож чадахгүй байв. Иймд тэрээр таны тусламжийг хүсжээ.

Бодлого нь дараах байдалтай байна: 2 ширхэг $f$ болон $g$ гэсэн 2-SAT томьёо өгөгдөх ба та тэдгээрийн боломжит хариултуудын олонлогууд нь ижилхэн эсэхийг тодорхойлох юм. Бусад тохиолдолд $f(x) ≠ g(x)$ байх $x$ хувьсагчдын утгуудын ямар нэгэн олонлогийг олно уу.

Оролт

Оролтын эхний мөрөнд 3 бүхэл тоо $n$, $m_{1}$ болон $m_{2}$ ($1 ≤ n ≤ 1000$, $1 ≤ m_{1}, m_{2} ≤ n^{2}$) өгөгдөх ба эдгээр нь харгалзан хувьсагчдын тоо, эхний томьёон доторх тусгаарлалтуудын тоо болон 2-дахь томьёон доторх тусгаарлалтуудын тоог тус тус илэрхийлнэ.

Дараагийн $m_{1}$ ширхэг мөрөнд $f$ буюу 2-SAT томьёоны тайлбар өгөгдөнө. Уг тайлбар нь яг $m_{1}$ ширхэг хос $x_{i}$ ($ - n ≤ x_{i} ≤ n, x_{i} ≠ 0$) бүхэл тоонуудаас тогтох бөгөөд хос бүр нь тусдаа салангид мөрөнд өгөгдсөн байх ба $x_{i} > 0$ нь үгүйсгэлгүй хувьсагчид харгалзах бол $x_{i} < 0$ нь үгүйсгэлтэй хувьсагчид харгалзах юм. Хос болгоны хооронд нэг ширхэг тусгаарлалт байна. Дараагийн $m_{2}$ ширхэг мөрөнд мөн ижил хэлбэрээр $g$ буюу 2-SAT томьёоны тайлбар өгөгдөнө.

Гаралт

Хэрэв 2 томьёо нь 2-уулаа ижилхэн хариултын олонлогтой байвал "SIMILAR" (хашилтгүйгээр) гэсэн ганц үгийг хэвлэнэ үү. Бусад тохиолдолд яг $n$ ширхэг бүхэл тоонууд $x_{i}$ ()-уудыг хэвлэх ба энэ нь $f(x) ≠ g(x)$ байх $x$-ын утгуудын ямар нэгэн олонлог байх юм.

Эхний жишээнд 2 тэнцүү томьёо өгөгдсөн байх ба иймд тэдгээр нь тодорхойлолт ёсоор ижилхэн байх юм.

2-дахь жишээнд хэрэв бид эхний функцийг $x_{1} = 0$ болон $x_{2} = 0$ гэсэн үед бодвол учраас хариу нь $0$ гарах юм. Гэвч 2-дахь томьёо нь учраас $1$-тэй тэнцүү болно. Иймд бид уг $x_{1} = 0$ болон $x_{2} = 0$ гэсэн $x$-ын утгуудын олонлогийг хариу болгон хэвлэхэд болох юм.