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$

5 4
3 1 -2 3
3 3 -4 -1
2 5 2
1 4

0 0 1 1 1

2 3
1 -1
1 -2
2 1 2

-1

출처

• 문제를 만든 사람: Diuven

• 문제를 검수한 사람: aeren, whqkrkt04