/*
考虑对树的深度奇偶分类，然后再在奇数层放球。
定义一个点的颜色(0/1) = 深度奇偶性 xor 球的有无；
容易得到初始状态是全 0，每次操作等价于球往相邻空位移动。

比较容易构造出最优的策略，每条边都贴下界。 
也就是说设有球点权 = 1，空位点权 = -1，
则 u 的子树和 sum 等价于 u->fa 移动球的次数(若 sum<0 则代表 fa->u )。 

考虑如果有奇环

偶环 
*/
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int N=100005;

int n,m,S,T,dep[N],fa[N],ord,dfn[N],f[N];
vector<int>G[N];
long long ans;

void link(int a,int b)
{
	G[a].push_back(b);
	G[b].push_back(a);
}

void dfs(int u,int par)
{
	fa[u]=par;
	dfn[u]=++ord;
	for(auto &v:G[u])
		if(v^par)
		{
			if(!dfn[v])
			{
				dep[v]=dep[u]+1;
				dfs(v,u);
			}
			else if(dfn[v]<dfn[u])
			{
				S=u;
				T=v;
			}
		}
}

void dfs1(int u)
{
	f[u]=dep[u]&1?1:-1;
	for(auto &v:G[u])
		if(fa[v]==u)
			dfs1(v),f[u]+=f[v];
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,a,b; i<=m; i++)
	{
		scanf("%d%d",&a,&b);
		link(a,b);
	}
	dep[1]=1;
	dfs(1,0);
	dfs1(1);
	if(n>m)
	{
		if(f[1])
			return puts("-1"),0;
	}
	else
	{
		if(dep[S]%2==dep[T]%2)
		{
			if(f[1]%2)
				return puts("-1"),0;
			ans+=abs(f[1]/2);
			for(int x=S; x!=T; x=fa[x])
				f[x]-=f[1]/2;
			for(int x=T; x; x=fa[x])
				f[x]-=f[1];
		}
		else
		{
			if(f[1])
				return puts("-1"),0;
			vector<int> v;
			for(int x=S; x!=T; x=fa[x])v.push_back(f[x]);
			v.push_back(0);
			nth_element(v.begin(),v.begin()+v.size()/2,v.end());
			int F=v[v.size()/2];
			ans+=abs(F);
			for(int x=S; x!=T; x=fa[x])f[x]-=F;
		}
	}
	for(int i=1; i<=n; i++)
		ans+=f[i]<0?-f[i]:f[i];
	printf("%lld\n",ans);
	return 0;
}

### Prompt

Create a solution in Cpp for the following problem:

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
/*
考虑对树的深度奇偶分类，然后再在奇数层放球。
定义一个点的颜色(0/1) = 深度奇偶性 xor 球的有无；
容易得到初始状态是全 0，每次操作等价于球往相邻空位移动。

比较容易构造出最优的策略，每条边都贴下界。 
也就是说设有球点权 = 1，空位点权 = -1，
则 u 的子树和 sum 等价于 u->fa 移动球的次数(若 sum<0 则代表 fa->u )。 

考虑如果有奇环

偶环 
*/
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int N=100005;

int n,m,S,T,dep[N],fa[N],ord,dfn[N],f[N];
vector<int>G[N];
long long ans;

void link(int a,int b)
{
	G[a].push_back(b);
	G[b].push_back(a);
}

void dfs(int u,int par)
{
	fa[u]=par;
	dfn[u]=++ord;
	for(auto &v:G[u])
		if(v^par)
		{
			if(!dfn[v])
			{
				dep[v]=dep[u]+1;
				dfs(v,u);
			}
			else if(dfn[v]<dfn[u])
			{
				S=u;
				T=v;
			}
		}
}

void dfs1(int u)
{
	f[u]=dep[u]&1?1:-1;
	for(auto &v:G[u])
		if(fa[v]==u)
			dfs1(v),f[u]+=f[v];
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,a,b; i<=m; i++)
	{
		scanf("%d%d",&a,&b);
		link(a,b);
	}
	dep[1]=1;
	dfs(1,0);
	dfs1(1);
	if(n>m)
	{
		if(f[1])
			return puts("-1"),0;
	}
	else
	{
		if(dep[S]%2==dep[T]%2)
		{
			if(f[1]%2)
				return puts("-1"),0;
			ans+=abs(f[1]/2);
			for(int x=S; x!=T; x=fa[x])
				f[x]-=f[1]/2;
			for(int x=T; x; x=fa[x])
				f[x]-=f[1];
		}
		else
		{
			if(f[1])
				return puts("-1"),0;
			vector<int> v;
			for(int x=S; x!=T; x=fa[x])v.push_back(f[x]);
			v.push_back(0);
			nth_element(v.begin(),v.begin()+v.size()/2,v.end());
			int F=v[v.size()/2];
			ans+=abs(F);
			for(int x=S; x!=T; x=fa[x])f[x]-=F;
		}
	}
	for(int i=1; i<=n; i++)
		ans+=f[i]<0?-f[i]:f[i];
	printf("%lld\n",ans);
	return 0;
}

```