問題文

$N$ 頂点 $M$ 辺の有向グラフが与えられます。 $i$ 番目 $(1\leq i\leq M)$ の辺は頂点 $U_i$ から $V_i$ に向かいます。この辺を $(U_i,\ V_i)$ で表します。グラフは多重辺や自己ループを含む場合があります。

重複を許す頂点の列 $(v_i)\ (1\leq v_i\leq N)$ を考え、 $(v_i)$ の長さを $L$ とします。任意の $i\ (1\leq i\leq L-1)$ について辺 $(v_i,\ v_{i+1})$ が存在するとき、列 $(v_1,\ (v_1,\ v_2),\ v_2,\ (v_2,\ v_3),\ v_3,\ \ldots,\ v_{L-1},\ (v_{L-1},\ v_L),\ v_L)$ を歩道と呼ぶことにします。

ルエルくんは、与えられたグラフに有向辺を有限回追加することで、全ての辺を $1$ 回だけ通る歩道が存在するようにしたいです。

すなわち、グラフに $K$ 本の辺 $(U_{M+i},\ V_{M+i})\ (1\leq i\leq K)$ を追加して $N$ 頂点 $(M+K)$ 辺の有向グラフにすることで、ある $(1,\ 2,\ \ldots,\ M+K)$ の順列 $(P_1,\ P_2,\ \ldots,\ P_{M+K})$ が存在して、任意の $i\ (1\leq i\leq M+K-1)$ について $V_{P_i}=U_{P_{i+1}}$ かつ、列 $(U_{P_1},\ (U_{P_1},\ V_{P_1}),\ V_{P_1},\ (U_{P_2},\ V_{P_2}),\ V_{P_2},\ \ldots,\ V_{P_{M+K-1}},\ (U_{P_{M+K}},\ V_{P_{M+K}}),\ V_{P_{M+K}})$ が歩道となるようにしたいです。

そのように辺を追加できる場合は、追加する辺の本数の最小値を出力してください。どのように辺を追加しても全ての辺を $1$ 回だけ通る歩道が存在しない場合には、-1を出力してください。

入力

$N\ M$
$U_1\ V_1$
$U_2\ V_2$
$U_3\ V_3$
$\vdots$
$U_M\ V_M$

• 入力は全て整数
• $1\leq N\leq 2\times 10^5$
• $1\leq M\leq 2\times 10^5$
• $1\leq U_i\leq N\ (1\leq i\leq M)$
• $1\leq V_i\leq N\ (1\leq i\leq M)$

出力

追加する辺の本数の最小値または-1を出力して、最後に改行してください。

サンプル

サンプル1

入力

4 7
1 2
1 3
1 4
2 1
3 1
3 4
4 2

出力

1

頂点 $2$ から頂点 $3$ へ向かう辺を追加すれば、全ての辺を $1$ 回だけ通る歩道が存在するようになります。

図にすると以下のようになります。

5 6
1 2
2 3
2 5
3 4
4 1
4 2

0

3 5
1 2
2 1
2 1
2 3
3 3

1

5 7
1 2
1 3
1 4
2 1
3 1
3 4
4 2

1