2-splniteľnosť

Literál je buď logická premenná, alebo jej negácia. (Napríklad $a$ alebo $\neg b$ sú literály.)

Literál nazveme kladný, ak je tvaru $a$, kde $a$ je premenná. V opačnom prípade je literál záporný. (Napríklad $a$ je kladný literál, a $\neg b$ je záporný literál.)

$k$-klauzula je logický výraz tvaru $a_1 \lor a_2 \lor \ldots \lor a_k$, kde $a_1, \ldots, a_k$ sú literály. Špeciálne, $2$-klauzula je logický výraz tvaru $a \lor b$ pre nejaké (nie nutne rôzne) literály $a, b$.

Príklady $2$-klauzúl: $a \lor \neg b$, $\neg x \lor \neg y$, $d \lor f$ ($a,b,x,y,d,f$ sú premenné).

Logický výraz je v \emph{konjunktívnej normálnej forme}, ak je v tvare $k_1 \land k_2 \land \ldots \land k_n$ pre nejaké klauzuly $k_1, k_2, \ldots, k_n$.

Na vstupe dostanete logický výraz v konjunktívnej normálnej forme, ktorého každá klauzula je $2$-klauzula. Zistite, či je tento logický výraz splniteľný — teda či vieme premenným vystupujúcim vo výraze priradiť pravdivostné hodnoty tak, aby bol výraz pravdivý.

Vstup

Na prvom riadku vstupu je číslo $t$ — počet testovacích vstupov. Každý vstup začína prázdnym riadkom, ktorý je nasledovaný riadkom s dvomi celými číslami $n, m$ — počet premenných a počet $2$-klauzúl. ($t \leq 1000$, $10 \leq n \leq 100\,000$, $0 \leq m \leq 500\,000$)

Nasleduje $m$ riadkov, $i$-ty z nich obsahuje čísla $a_i$ a $b_i$ a popisuje $i$-tu klauzulu výrazu.

Celý logický výraz vieme z tohto zápisu zostrojiť ako $(L_{a_1} \lor L_{b_1}) \land (L_{a_2} \lor L_{b_2}) \land \ldots \land (L_{a_m} \lor L_{b_m})$.

$a_i, b_i \in \lbrace 1, 2, \ldots, n \rbrace \cup \lbrace -1, -2, \ldots, -n \rbrace$
$L_1, \ldots, L_n$ reprezentujú kladné literály (teda premenné)
$L_{-1}, \ldots, L_{-n}$ reprezentujú záporné literály (negácie daných premenných) konkrétne, $L_{-i}$ je $\neg L_i$.

Výstup

Pre každý vstup vypíšte na samostatný riadok $-1$, ak sa výraz nedá splniť (teda ak pre ľubovoľné ohodnotenie premenných je výraz nepravdicý — príkladom takéhoto výrazu je $(a \lor a) \land (\neg a \lor \neg a)$.

Ak sa výraz na vstupe dá splniť, vypíšte do jedného riadku $n$ čísel z $\lbrace 0, 1 \rbrace$ — jedno možné priradenie hodnôt premenným. ($i$-te číslo popisuje $i$-tu premennú, teda $L_i$.) Ak je možných riešení viacero, vypíšte ľubovoľné z nich.

Príklad

Vstup

Výstup

0 0 0 0 1
0 0 0 1 0

Prvý vstup popisuje nasledovný logický výraz: $(\neg L_4 \lor \neg L_2) \land (\neg L_3 \lor \neg L_1) \land (L_3 \lor \neg L_4) \land (L_4 \lor L_5) \land (\neg L_3 \lor L_4)$. Priradenie hodnôt v riešení je $L_1 = 0, L_2 = 0, L_3 = 0, L_4 = 0, L_5 = 1$, prvá klauzula je pravdivá, lebo $\neg L_2 = 1$, druhá lebo $\neg L_3 = 1$ atď. Keďže všetky klauzuly sú pravdivé (majú hodnotu 1), je aj celý logický výraz pravdivý.