21732번 - SAT-2 스페셜 저지

0 또는 1의 값을 가질 수 있는 boolean 변수 $n$ 개 $x_1, x_2, x_3, \cdots x_n$ 가 있다.

변수들과 변수들의 부정들의 논리합만으로 이루어진 표현을 절(Clause)라고 한다. 예를 들어, $\lnot x_1 \lor \lnot x_4 \lor x_7$ 와 $x_2$, 와 $x_3 \lor \lnot x_8 \lor x_8 \lor x_{5}$ 는 각각 모두 절이지만, $x_5 \land \lnot x_6$은 논리곱이 포함되어 있으므로 절이 아니다.

위와 같이 정의된 절들의 논리곱만으로 이루어진 식들을 CNF (Conjunctive/Clausal Normal Form)이라고 부른다. 예를 들어, $(\lnot x_1 \lor \lnot x_4 \lor x_7) \land (x_2 \lor x_4)$는 CNF이다.

$n$개의 변수와 $m$개의 절로 이루어진 CNF 식이 입력으로 주어진다. 주어진 CNF 식에 각 변수가 (그것의 부정을 포함하여) 최소 0번, 최대 2번 등장할 때, 주어진 CNF 식의 값을 참이 되도록 하는 변수들의 값을 구하여라. 만약 그러한 변수들의 값이 존재하지 않는다면 -1을 출력하라.

입력의 첫 줄에 정수 $n, m$이 주어진다.

이후 $m$개의 줄 중에서 $i$번째 줄에는 각 절에 속한 항의 개수를 나타내는 $k_i$와, 각 항을 의미하는 $k_i$개의 정수 $l_{i, j}$가 순서대로 주어진다. $l_{i,j}$가 양수이면 그 항은 $x_{l_{i,j}}$을 의미하고, 음수이면 $\lnot x_{-l_{i,j}}$를 의미한다.

식을 만족시키는 변수들의 값이 존재한다면 한 줄에 각 변수들의 값을 공백으로 분리하여 순서대로 출력한다. 가능한 값이 여러 개 있다면, 그 중 아무거나 출력해도 된다.

만약 그러한 변수들의 값이 존재하지 않는다면, 첫 줄에 -1을 출력한다.

• $1 \le n, m \le 100\,000$
• $1 \le k_i \le 100\,000$
• $1 \le |l_{i,j}| \le n$