Loading...
$N$개의 불리언 변수 $x_1, x_2, \dots, x_N$과 $M$개의 절(clause)이 주어진다. 각 절은 두 리터럴의 논리합(OR) 형태로 이루어져 있다. 모든 절을 동시에 만족하는 변수의 참, 거짓 할당이 존재하는지 판별하는 프로그램을 작성하라.
첫째 줄에 변수의 개수 $N$과 절의 개수 $M$이 공백으로 구분되어 주어진다.
둘째 줄부터 $M$개의 줄에 걸쳐 각 절의 정보가 주어진다. 각 줄에는 두 개의 정수가 공백으로 구분되어 주어지며, $1$ 이상 $N$ 이하의 양의 정수 $i$는 $x_i$를, $-N$ 이상 $-1$ 이하의 음의 정수 $-i$는 $\neg x_i$(NOT $x_i$)를 나타낸다.
모든 절을 만족하는 변수 할당이 존재하면 첫째 줄에 YES를, 존재하지 않으면 NO를 출력하라.
3 3
1 2
-1 3
-2 -3
YES
1 2
1 1
-1 -1
NO