Unsatisfying

A computer scientist usually tries to satisfy a set of constraints. This time you do the opposite and make a list of logical statements unsatisfiable.

You are given a list of logical statements of the following form:

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

Each $p_i$ is a proposition that is either true or false. The disjunction operator $\lor$ is read as logical OR. The symbol $\neg$ is negation, which flips the value of the proposition that follows it from true to false and from false to true.

To satisfy a list of logical statements, you must assign true or false to each proposition so that every disjunction in the list evaluates to true.

Your task is to add disjunctions to the list so that the whole list becomes unsatisfiable. The disjunctions you add cannot use the negation symbol.

Every disjunction, both the given ones and the ones you add, has exactly two terms.

The first line contains two integers $n$ and $m$ separated by a space ($1 \le n, m \le 2000$). Here $n$ is the number of propositions and $m$ is the number of disjunctions.

Each of the next $m$ lines contains two integers $a_i$ and $b_i$ separated by a space ($1 \le |a_i|, |b_i| \le n$), describing the two propositions of the $i$-th disjunction. A positive $a_i$ means the proposition $p_{a_i}$, and a negative $a_i$ means the negated proposition $\neg p_{|a_i|}$. Read $b_i$ the same way.

The second sample input corresponds to the following list of logical statements:

$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.$

Print on a single line one integer, the minimum number of disjunctions you must add to make the list unsatisfiable. If the list cannot be made unsatisfiable, print $-1$ instead. Each disjunction you add consists of two propositions, the two propositions do not have to be distinct, and neither of them may be negated.

In the second sample, adding the disjunction $p_2 \lor p_2$ makes the list unsatisfiable.