[AGC004F] Namori

题意翻译

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

题目描述

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

输入输出格式

输入格式


The input is given from Standard Input in the following format: ``` $ N $ $ M $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ : $ $ a_M $ $ b_M $ ```

输出格式


If it is possible to turn all the vertices black, print the minimum number of times the operation needs to be performed in order to achieve the objective. Otherwise, print `-1` instead.

输入输出样例

输入样例 #1

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

输出样例 #1

5

输入样例 #2

3 2
1 2
2 3

输出样例 #2

-1

输入样例 #3

4 4
1 2
2 3
3 4
4 1

输出样例 #3

2

输入样例 #4

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

输出样例 #4

7

输入样例 #5

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

输出样例 #5

5

输入样例 #6

3 2
1 2
2 3

输出样例 #6

-1

输入样例 #7

4 4
1 2
2 3
3 4
4 1

输出样例 #7

2

输入样例 #8

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

输出样例 #8

7

说明

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ N-1\ \leq\ M\ \leq\ N $ - $ 1\ \leq\ a_i,b_i\ \leq\ N $ - グラフには自己ループや多重辺はない。 - グラフは連結である。 ### 部分点 - $ 1500 $ 点分のデータセットでは、 $ M=N-1 $ が成り立つ。 ### Problem Statement You are given an undirected graph with $ N $ vertices and $ M $ edges. Here, $ N-1\ \leq\ M\ \leq\ N $ holds and the graph is connected. There are no self-loops or multiple edges in this graph. The vertices are numbered $ 1 $ through $ N $ , and the edges are numbered $ 1 $ through $ M $ . Edge $ i $ connects vertices $ a_i $ and $ b_i $ . The color of each vertex can be either white or black. Initially, all the vertices are white. Snuke is trying to turn all the vertices black by performing the following operation some number of times: - Select a pair of adjacent vertices with the same color, and invert the colors of those vertices. That is, if the vertices are both white, then turn them black, and vice versa. Determine if it is possible to turn all the vertices black. If the answer is positive, find the minimum number of times the operation needs to be performed in order to achieve the objective. ### Constraints - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ N-1\ \leq\ M\ \leq\ N $ - $ 1\ \leq\ a_i,b_i\ \leq\ N $ - There are no self-loops or multiple edges in the given graph. - The given graph is connected. ### Partial Score - In the test set worth $ 1500 $ points, $ M=N-1 $ . ### Sample Explanation 1 例えば、図のように操作を行えばよいです。 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT2046/c8b11b1acfd9f774e00ad02846e7a5740c1d2263.png) ### Sample Explanation 2 すべての頂点を黒にすることはできません。 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT2046/20897ee8d3fa07eff68530f736f4b0a7c8d526b3.png) ### Sample Explanation 3 このケースは部分点のデータセットには含まれません。 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT2046/ae664bb6685375d5072657f8ba4253391ea56c82.png) ### Sample Explanation 4 このケースは部分点のデータセットには含まれません。 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT2046/7c671be548c68ecb920458e0bfea12e53b9cc637.png) ### Sample Explanation 5 For example, it is possible to perform the operations as shown in the following diagram: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT2046/c8b11b1acfd9f774e00ad02846e7a5740c1d2263.png) ### Sample Explanation 6 It is not possible to turn all the vertices black. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT2046/20897ee8d3fa07eff68530f736f4b0a7c8d526b3.png) ### Sample Explanation 7 This case is not included in the test set for the partial score. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT2046/ae664bb6685375d5072657f8ba4253391ea56c82.png) ### Sample Explanation 8 This case is not included in the test set for the partial score. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT2046/7c671be548c68ecb920458e0bfea12e53b9cc637.png)