智慧熱橋

智慧熱橋是雲之大陸中架起的天空之橋，阿卡西亞全餐菜單飲品ATOM所在地。當初為藍色尼特羅為了行走自如之下，讓它們的奴隸（紅色尼特羅）建造此橋。

image alt

這座橋可以看成是由$n$個布林變數$P_1\sim P_n$(只能是true或是false)所組成的，雲之大陸惡劣的環境下產生了$m$個限制條件，只要這些變數存在一組解能讓所有限制條件都是true那這座橋就會非常穩定(反之為不穩定)，所有限制條件的格式只會是以下4種：

$a\lor b$
$\neg a\lor b$
$a\lor\neg b$
$\neg a\lor\neg b$

其中$\neg$符號表示取反，如果變數$x$是true，$\neg x$就是false；如果變數$x$是false，$\neg x$就是true。 $\lor$符號表是邏輯上的or，也就是說左右兩邊的結果都是false時限制條件的結果就會是false，除此之外限制條件的結果會是true。

舉例來說，現在有兩個變數$a=true,b=false$，則條件

$a\lor b$ 的結果是true
$\neg a\lor b$ 的結果是false
$a\lor\neg b$ 的結果是true
$\neg a\lor\neg b$ 的結果是true

今天你要帶領紅色尼特羅們反抗藍色尼特羅，所以你決定要偷偷破壞智慧熱橋。你可透過體內龐大的能量製造更多的限制條件，但是人類的能力有限你所製造的限制條件中不可以出現$\neg$符號。由於製造限制條件會消耗掉巨大的熱量所以你希望製造盡量少的條件就能讓智慧熱橋處於不穩定的狀態，請問你最少需要製造幾個限制條件來達到目的呢?

輸入

第一行有兩個正整數$n,m(1 \le n,m \le 2000)$以空白隔開，表示有$n$個布林變數$P_1\sim P_n$以及$m$個條件。

接下來有$m$行，每行有兩個整數$a,b(1 \le |a|,|b|\le n)$以空白隔開，表示限制條件$P_a\lor P_b$。負號表示$\neg$符號，以$a$為例，如果$a<0$，則限制條件中的變數為$\neg P_{|a|}$。

範例輸入2的限制條件如下：

$P_1\lor P_2$
$\neg P_1\lor \neg P_3$
$\neg P_2\lor P_3$
$P_3\lor \neg P_4$
$\neg P_2\lor \neg P_3$

輸出

輸出最少需要製造幾個限制條件才能讓智慧熱橋處於不穩定的狀態，答案可能為$0$。如果無解請輸出$-1$。

範例輸入2中只要增加條件$P_2\lor P_2$就能讓橋變得不穩定。

範例輸入1

2 1
1 2

範例輸出1

-1

範例輸入2

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

範例輸出2

Judge Setting

run-time limit: 1000 ms
memory limit: 655360000 byte
測資數量: 17