[AGC004F] Namori

给定一个 $N$ 个点，$M$ 条边的图，没有自环，没有重边。其中 $N-1\le M\le N$，每个点初始是白色。每次操作可以处理一条边，其两个点如果颜色相同则都变成相反的颜色（黑变白，白变黑）。询问能否将每个点都变为黑色。如果能，输出最少的操作数；如果不能，输出 $-1$. Translated by @naive_wcx

[problemUrl]: https://atcoder.jp/contests/agc004/tasks/agc004_f $ N $ 頂点 $ M $ 辺の無向グラフがあります。 ただし、$ N-1\ <\ =M\ <\ =N $ であり、グラフは連結です。 また、グラフには自己ループや多重辺はありません。 頂点は $ 1 $ から $ N $ まで番号が振られており、辺は $ 1 $ から $ M $ まで番号が振られています。 辺 $ i $ は頂点 $ a_i $ と $ b_i $ を結んでいます。 各頂点は白または黒になることができます。 最初、すべての頂点は白です。 高橋君は次の操作を何回か行い、すべての頂点を黒にしようとしています。 - 隣り合う同色の頂点のペアを選び、それらの色をともに反転する。 すなわち、ともに白ならばともに黒へ変え、ともに黒ならばともに白へ変える。 すべての頂点を黒にすることができるか判定し、できるならば必要な操作回数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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

### 制約 - $ 2\ <\ =N\ <\ =10^5 $ - $ N-1\ <\ =M\ <\ =N $ - $ 1\ <\ =a_i，b_i\ <\ =N $ - グラフには自己ループや多重辺はない。 - グラフは連結である。 ### 部分点 - $ 1500 $ 点分のデータセットでは、$ M=N-1 $ が成り立つ。 ### Sample Explanation 1 例えば、図のように操作を行えばよいです。 !\[\](/img/agc/004/gatbantar/F\_1.png) ### Sample Explanation 2 すべての頂点を黒にすることはできません。 !\[\](/img/agc/004/gatbantar/F\_2.png) ### Sample Explanation 3 このケースは部分点のデータセットには含まれません。 !\[\](/img/agc/004/gatbantar/F\_3.png) ### Sample Explanation 4 このケースは部分点のデータセットには含まれません。 !\[\](/img/agc/004/gatbantar/F\_4.png)