/*
https://www.luogu.com.cn/blog/flashblog/solution-at2046

树 是 二 分 图！！！

也许看到这种反转题第一步就应该按照深度什么的来个黑白反转。。？这样才能进展qwq。。
还有，环套树也要考虑奇环和偶环哦！

这种转化下，将相邻两个同色同时反转 等价于 将相邻两个是否有硬币情况交换一下
奇环：断掉的边只有分摊部分转移、加快运输的作用
*/
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 2e5 + 10;
int n, m, ans, stx, sty, fx, fy;
int to[N << 1], nxt[N << 1], lnk[N], cnt;
int dep[N], fa[N], s[N], a[N], top;

void add(int x, int y) {
    to[++cnt] = y, nxt[cnt] = lnk[x], lnk[x] = cnt;
}

int getfa(int x) {
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}

void dfs(int x, int f, int val) {
    dep[x] = dep[f] + 1;
    fa[x] = f;
    s[x] = val;
    for (int i = lnk[x]; i; i = nxt[i]) {
        int y = to[i];
        if (y != f)
            dfs(y, x, -val), s[x] += s[y];
    }
}

int main() {
    cin >> n >> m;
    rep(i, 1, n) fa[i] = i;
    stx = sty = 1;
    rep(i, 1, m) {
        int x, y; scanf("%d%d", &x, &y);
        if ((fx = getfa(x)) != (fy = getfa(y))) fa[fx] = fy;
        else { stx = x, sty = y; continue; }  // 环上边，给它断掉！
        add(x, y), add(y, x);
    }
    dfs(stx, 0, 1);
    if (n == m) {
        for (int i = sty; i; i = fa[i]) a[++top] = s[i];
        if ((dep[stx] - dep[sty]) & 1) {  // 偶环
            if (s[stx]) return puts("-1"), 0;
            sort(a + 1, a + top + 1);
            for (int i = sty; i; i = fa[i]) s[i] -= a[top >> 1];
        } else {  // 奇环
            if (s[stx] & 1) return puts("-1"), 0;
            for (int i = sty; i; i = fa[i]) s[i] -= s[stx] >> 1;
        }
    } else if (s[stx]) return puts("-1"), 0;
    rep(i, 1, n) ans += abs(s[i]);
    return printf("%d\n", ans), 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

You are given an undirected graph with N vertices and M edges. Here, N-1≤M≤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≤N≤10^5
* N-1≤M≤N
* 1≤a_i,b_i≤N
* There are no self-loops or multiple edges in the given graph.
* The given graph is connected.

Input

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


Output

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.

Examples

Input

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


Output

5


Input

3 2
1 2
2 3


Output

-1


Input

4 4
1 2
2 3
3 4
4 1


Output

2


Input

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


Output

7

### Response

```cpp
/*
https://www.luogu.com.cn/blog/flashblog/solution-at2046

树 是 二 分 图！！！

也许看到这种反转题第一步就应该按照深度什么的来个黑白反转。。？这样才能进展qwq。。
还有，环套树也要考虑奇环和偶环哦！

这种转化下，将相邻两个同色同时反转 等价于 将相邻两个是否有硬币情况交换一下
奇环：断掉的边只有分摊部分转移、加快运输的作用
*/
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 2e5 + 10;
int n, m, ans, stx, sty, fx, fy;
int to[N << 1], nxt[N << 1], lnk[N], cnt;
int dep[N], fa[N], s[N], a[N], top;

void add(int x, int y) {
    to[++cnt] = y, nxt[cnt] = lnk[x], lnk[x] = cnt;
}

int getfa(int x) {
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}

void dfs(int x, int f, int val) {
    dep[x] = dep[f] + 1;
    fa[x] = f;
    s[x] = val;
    for (int i = lnk[x]; i; i = nxt[i]) {
        int y = to[i];
        if (y != f)
            dfs(y, x, -val), s[x] += s[y];
    }
}

int main() {
    cin >> n >> m;
    rep(i, 1, n) fa[i] = i;
    stx = sty = 1;
    rep(i, 1, m) {
        int x, y; scanf("%d%d", &x, &y);
        if ((fx = getfa(x)) != (fy = getfa(y))) fa[fx] = fy;
        else { stx = x, sty = y; continue; }  // 环上边，给它断掉！
        add(x, y), add(y, x);
    }
    dfs(stx, 0, 1);
    if (n == m) {
        for (int i = sty; i; i = fa[i]) a[++top] = s[i];
        if ((dep[stx] - dep[sty]) & 1) {  // 偶环
            if (s[stx]) return puts("-1"), 0;
            sort(a + 1, a + top + 1);
            for (int i = sty; i; i = fa[i]) s[i] -= a[top >> 1];
        } else {  // 奇环
            if (s[stx] & 1) return puts("-1"), 0;
            for (int i = sty; i; i = fa[i]) s[i] -= s[stx] >> 1;
        }
    } else if (s[stx]) return puts("-1"), 0;
    rep(i, 1, n) ans += abs(s[i]);
    return printf("%d\n", ans), 0;
}

```