시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1536 MB 47 10 10 22.727%

문제

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$

예제 입력 1

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

예제 출력 1

0 0 1 1 1

$(x_1 \lor \lnot x_2 \lor x_3) \land (x_3 \lor \lnot x_4 \lor \lnot x_1) \land (x_5 \lor x_2) \land (x_4)$

여러 값들 중 $(x_1, x_2, x_3, x_4, x_5) = (0,0,1,1,1)$이 가능하다.

예제 입력 2

2 3
1 -1
1 -2
2 1 2

예제 출력 2

-1

$(\lnot x_1) \land (\lnot x_2) \land (x_1 \lor x_2)$

이 식을 만족하는 변수들의 값은 존재하지 않는다.

출처

Contest > IDTcup > 제 3회 IDTcup H번