충족 불가능하게 만들기

보통 컴퓨터 과학자는 주어진 제약을 만족시키려고 한다. 이번에는 반대로 논리식 목록을 충족 불가능하게 만들어야 한다.

다음과 같은 형태의 논리식 목록이 주어진다.

$p_1 \lor p_2, \qquad \neg p_2 \lor p_3, \qquad p_3 \lor \neg p_4.$

각 $p_i$는 true 또는 false 중 하나가 되는 명제다. 논리합 기호 $\lor$는 논리 OR로 해석한다. $\neg$ 기호는 부정이며, 바로 뒤에 오는 명제의 값을 true에서 false로, false에서 true로 뒤집는다.

논리식 목록을 충족시킨다는 것은 각 명제에 true 또는 false를 할당해서 목록에 있는 모든 논리합이 true가 되게 하는 것이다.

당신이 할 일은 목록에 논리합을 추가해서 목록 전체를 충족 불가능하게 만드는 것이다. 단, 추가하는 논리합에는 부정 기호를 쓸 수 없다.

주어진 논리합과 추가하는 논리합 모두 항이 정확히 2개다.

첫째 줄에 정수 $n$과 $m$이 공백으로 구분되어 주어진다 ($1 \le n, m \le 2000$). $n$은 명제의 개수, $m$은 논리합의 개수다.

다음 $m$개 줄에는 각각 정수 $a_i$와 $b_i$가 공백으로 구분되어 주어지며 ($1 \le |a_i|, |b_i| \le n$), $i$번째 논리합을 이루는 두 명제를 나타낸다. $a_i$가 양수면 명제 $p_{a_i}$를 뜻하고, 음수면 부정된 명제 $\neg p_{|a_i|}$를 뜻한다. $b_i$도 같은 방식으로 읽는다.

두 번째 예제 입력은 다음 논리식 목록에 대응한다.

$p_1 \lor p_2, \quad \neg p_1 \lor \neg p_3, \quad \neg p_2 \lor p_3, \quad p_3 \lor \neg p_4, \quad \neg p_2 \lor \neg p_3.$

목록을 충족 불가능하게 만들려면 논리합을 최소 몇 개 더 추가해야 하는지, 그 개수를 한 줄에 정수 하나로 출력한다. 충족 불가능하게 만들 수 없으면 대신 $-1$을 출력한다. 추가하는 각 논리합은 명제 두 개로 이루어지며, 두 명제가 같아도 된다. 부정된 명제는 쓸 수 없다.

두 번째 예제에서는 $p_2 \lor p_2$를 추가하면 목록이 충족 불가능해진다.