题目描述

$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 を出力せよ。

题目大意

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

Translated by @naive_wcx

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

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

Sample Explanation 2

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

Sample Explanation 3

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

Sample Explanation 4

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