配点 : $2200$ 点

問題文

$N$ 頂点 $M$ 辺の無向グラフがあります。 ただし、$N-1 \leq M \leq N$ であり、グラフは連結です。 また、グラフには自己ループや多重辺はありません。

頂点は $1$ から $N$ まで番号が振られており、辺は $1$ から $M$ まで番号が振られています。 辺 $i$ は頂点 $a_i$ と $b_i$ を結んでいます。

各頂点は白または黒になることができます。 最初、すべての頂点は白です。 高橋君は次の操作を何回か行い、すべての頂点を黒にしようとしています。

• 隣り合う同色の頂点のペアを選び、それらの色をともに反転する。 すなわち、ともに白ならばともに黒へ変え、ともに黒ならばともに白へ変える。

すべての頂点を黒にすることができるか判定し、できるならば必要な操作回数の最小値を求めてください。

制約

• $2 \leq N \leq 10^5$
• $N-1 \leq M \leq N$
• $1 \leq a_i,b_i \leq N$
• グラフには自己ループや多重辺はない。
• グラフは連結である。

部分点

• $1500$ 点分のデータセットでは、$M=N-1$ が成り立つ。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$a_1$ $b_1$

$a_2$ $b_2$

$:$

$a_M$ $b_M$

出力

すべての頂点を黒にすることができるならば、必要な操作回数の最小値を出力せよ。 できないならば、代わりに -1 を出力せよ。

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

5

例えば、図のように操作を行えばよいです。

3 2
1 2
2 3

-1

すべての頂点を黒にすることはできません。

4 4
1 2
2 3
3 4
4 1

2

このケースは部分点のデータセットには含まれません。

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

7

このケースは部分点のデータセットには含まれません。