NOT a SAT 문제

SAT 문제는 주어진 CNF가 참이 되도록 논리 변수에 참과 거짓을 적절히 배정할 수 있는지 판별하는 문제이다.

• CNF는 하나 이상의 절이 $\wedge$ (논리곱)로 연결된 논리식이다.
• 절은 논리 변수 또는 논리 변수의 부정이 하나 이상 $\vee$ (논리합)로 연결된 논리식이다.

예를 들어 $(x_1\vee x_2\vee\neg x_3)$와 $(x_2\vee\neg x_4\vee\neg x_2\vee\neg x_4)$는 절이다. 두 절을 이으면 $(x_1\vee x_2\vee\neg x_3)\wedge(x_2\vee\neg x_4\vee\neg x_2\vee\neg x_4)$인 CNF가 된다.

이 문제는 SAT 문제가 아니다. 이 문제에서는 CNF를 참으로 만드는 대신 CNF를 거짓으로 만들어야 한다.

첫째 줄에 논리 변수의 개수 $N$과 CNF에 있는 절의 개수 $M$이 주어진다. ($1 \le N \le 500000$, $1 \le M \le 200000$)

둘째 줄부터 $M$개의 줄에 각 절의 정보가 주어진다. 각 줄의 첫 번째 정수 $k$는 절에 있는 논리 변수의 개수이며 ($1 \le k \le 200000$), 이어서 $k$개의 정수 $a$가 공백으로 구분되어 주어진다. $a$가 양수이면 $x_a$가 절에 들어 있고, 음수이면 $\neg x_{|a|}$가 절에 들어 있다 ($1 \le |a| \le N$).

모든 줄의 $k$의 합은 500000 이하이다.

첫째 줄에 CNF의 결과를 거짓으로 만들 수 있다면 YES를, 없다면 NO를 출력한다.

CNF의 결과를 거짓으로 만들 수 있다면 둘째 줄에 CNF의 값을 거짓으로 만드는 $x_1, x_2, \ldots, x_N$의 값을 공백으로 구분하여 출력한다. $x_i$가 참이면 $1$을, 거짓이면 $0$을 출력한다. 가능한 배정이 여러 가지라면 그중 아무거나 하나를 출력한다.