Language: C++

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?n:-n;
	}
}
struct edge
{
	int to;
	int next;
}e[333333];
int pe=111111;
int deg[111111];
void insert(int a,int to)
{
	e[pe]=(edge){to,e[a].next};
	e[a].next=pe++;
	++deg[to];
}
int siz[111111][2];
int c[111111];
int q[111111],hq,tq;
int cyc[111111];
long long ans;
void dfs(int o,int fa)
{
	siz[o][c[o]]=1,siz[o][!c[o]]=0;
	for(register int p=e[o].next;p;p=e[p].next)
		if(e[p].to!=fa)
		{
			c[e[p].to]=!c[o];
			dfs(e[p].to,o);
			siz[o][0]+=siz[e[p].to][0];
			siz[o][1]+=siz[e[p].to][1];
		}
	int d=dmin(siz[o][0],siz[o][1]);
	siz[o][0]-=d,siz[o][1]-=d;
	ans+=siz[o][0]+siz[o][1];
}
int pv,cnt[222222][2],d[222222][2];
void dfs2(int o,int fa)
{
	siz[o][0]=1;
	siz[o][1]=0;
	for(register int p=e[o].next;p;p=e[p].next)
		if(e[p].to!=fa&&!cyc[e[p].to])
		{
			dfs2(e[p].to,o);
			siz[o][0]+=siz[e[p].to][1];
			siz[o][1]+=siz[e[p].to][0];
		}
	int d=dmin(siz[o][0],siz[o][1]);
	siz[o][0]-=d,siz[o][1]-=d;
	ans+=siz[o][0]+siz[o][1];
}
void dfs3(int o,int fa,int top)
{
	dfs2(o,o);
	++pv;
	cnt[pv][0]=siz[o][0];
	cnt[pv][1]=siz[o][1];
	ans-=siz[o][0]+siz[o][1];
	for(register int p=e[o].next;p;p=e[p].next)
		if(e[p].to!=fa&&e[p].to!=top&&cyc[e[p].to])
		{
			dfs3(e[p].to,o,top);
			return;
		}
}
#define ab(x) ((x)>0?(x):-(x))
int main()
{
	//freopen("reverse.in","r",stdin);
	//freopen("reverse.out","w",stdout);
	//int T=io::F();
	//while(T--)
	{
		pe=111111;
		for(register int i=1;i<=pe;++i)e[i].next=0;
		memset(deg,0,sizeof(deg));
		int n=io::F(),m=io::F();
		for(register int i=1;i<=m;++i)
		{
			int x=io::F(),y=io::F();
			insert(x,y);
			insert(y,x);
		}
		if(n&1){puts("-1");continue;}
		if(m==n-1)
		{
			ans=0;
			dfs(1,1);
			if(siz[1][0]||siz[1][1]){puts("-1");continue;}
			printf("%lld\n",ans);
			continue;
		}
		else
		{
			int md=0;
			for(register int i=1;i<=n;++i)cmax(md,deg[i]);
			if(md==2){printf("%d\n",n/2);continue;}
			hq=tq=1;
			for(register int i=1;i<=n;++i)
				if(deg[i]==1)q[tq++]=i,cyc[i]=0;
					else cyc[i]=1;
			for(;hq!=tq;++hq)
				for(register int p=e[q[hq]].next;p;p=e[p].next)
					if(--deg[e[p].to]==1)q[tq++]=e[p].to,cyc[e[p].to]=0;
			ans=0;
			pv=0;
			for(register int i=1;i<=n;++i)
				if(cyc[i]){dfs3(i,i,i);break;}
			int sum=0;
			for(register int i=1;i<=pv;++i)
				sum+=cnt[i][0]+cnt[i][1];//cnt[pv+i][0]=cnt[i][0],cnt[pv+i][1]=cnt[i][1];
			sum/=2;
			if((long long)sum*4*pv>=20000000)sum=5000000/pv;
			long long rr=0x3f3f3f3f3f3f3f3fll;
			for(register int i=0;i<=sum;++i)
			{
				long long tmp=ab(i);
				for(register int j=1;j<=pv;++j)d[j][0]=cnt[j][0],d[j][1]=cnt[j][1];
				d[pv][0]-=i,d[1][1]+=i;
				for(register int j=1;j<pv;++j)
				{
					int min=dmin(d[j][0],d[j][1]);
					d[j][0]-=min;
					d[j][1]-=min;
					tmp+=ab(d[j][0]+d[j][1]);
					d[j+1][0]+=d[j][1];
					d[j+1][1]+=d[j][0];
				}
				if(d[pv][0]==d[pv][1])cmin(rr,tmp);
			}
			for(register int i=0;i<=sum;++i)
			{
				long long tmp=ab(i);
				for(register int j=1;j<=pv+1;++j)d[j][0]=cnt[j][0],d[j][1]=cnt[j][1];
				d[pv][1]-=i,d[1][0]+=i;
				for(register int j=1;j<pv;++j)
				{
					int min=dmin(d[j][0],d[j][1]);
					d[j][0]-=min;
					d[j][1]-=min;
					tmp+=ab(d[j][0]+d[j][1]);
					d[j+1][0]+=d[j][1];
					d[j+1][1]+=d[j][0];
				}
				if(d[pv][0]==d[pv][1])cmin(rr,tmp);
			}
			for(register int i=0;i<=sum;++i)
			{
				long long tmp=ab(i);
				for(register int j=1;j<=pv;++j)d[j][0]=cnt[j][0],d[j][1]=cnt[j][1];
				d[pv][0]+=i,d[1][1]-=i;
				for(register int j=pv;j>1;--j)
				{
					int min=dmin(d[j][0],d[j][1]);
					d[j][0]-=min;
					d[j][1]-=min;
					tmp+=ab(d[j][0]+d[j][1]);
					d[j-1][0]+=d[j][1];
					d[j-1][1]+=d[j][0];
				}
				if(d[1][0]==d[1][1])cmin(rr,tmp);
			}
			for(register int i=0;i<=sum;++i)
			{
				long long tmp=ab(i);
				for(register int j=1;j<=pv;++j)d[j][0]=cnt[j][0],d[j][1]=cnt[j][1];
				d[pv][1]+=i,d[1][0]-=i;
				for(register int j=pv;j>1;--j)
				{
					int min=dmin(d[j][0],d[j][1]);
					d[j][0]-=min;
					d[j][1]-=min;
					tmp+=ab(d[j][0]+d[j][1]);
					d[j-1][0]+=d[j][1];
					d[j-1][1]+=d[j][0];
				}
				if(d[1][0]==d[1][1])cmin(rr,tmp);
			}
			if(rr==0x3f3f3f3f3f3f3f3fll)puts("-1");
				else printf("%lld\n",ans+rr);
		}
	}
	return 0;
}

Compiler output:
a.cc: In function 'void dfs(int, int)':
a.cc:45:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   45 |         for(register int p=e[o].next;p;p=e[p].next)
      |                          ^
a.cc: In function 'void dfs2(int, int)':
a.cc:62:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   62 |         for(register int p=e[o].next;p;p=e[p].next)
      |                          ^
a.cc: In function 'void dfs3(int, int, int)':
a.cc:80:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   80 |         for(register int p=e[o].next;p;p=e[p].next)
      |                          ^
a.cc: In function 'int main()':
a.cc:96:34: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   96 |                 for(register int i=1;i<=pe;++i)e[i].next=0;
      |                                  ^
a.cc:99:34: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   99 |                 for(register int i=1;i<=m;++i)
      |                                  ^
a.cc:105:36: error: continue statement not within a loop
  105 |                 if(n&1){puts("-1");continue;}
      |                                    ^~~~~~~~
a.cc:110:61: error: continue statement not within a loop
  110 |                         if(siz[1][0]||siz[1][1]){puts("-1");continue;}
      |                                                             ^~~~~~~~
a.cc:112:25: error: continue statement not within a loop
  112 |                         continue;
      |                         ^~~~~~~~
a.cc:117:42: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  117 |                         for(register int i=1;i<=n;++i)cmax(md,deg[i]);
      |                                          ^
a.cc:118:54: error: continue statement not within a loop
  118 |                         if(md==2){printf("%d\n",n/2);continue;}
      |                                                      ^~~~~~~~
a.cc:120:42: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  120 |                         for(register int i=1;i<=n;++i)
      |                                          ^
a.cc:124:50: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  124 |                                 for(register int p=e[q[hq]].next;p;p=e[p].next)
      |                                                  ^
a.cc:128:42: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  128 |                         for(register int i=1;i<=n;++i)
      |                                          ^
a.cc:131:42: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  131 |                         for(register int i=1;i<=pv;++i)
      |                                          ^
a.cc:136:42: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  136 |                         for(register int i=0;i<=sum;++i)
      |                                          ^
a.cc:139:50: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  139 |                                 for(register int j=1;j<=pv;++j)d[j][0]=cnt[j][0],d[j][1]=cnt[j][1];
      |                                                  ^
a.cc:141:50: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  141 |                                 for(register int j=1;j<pv;++j)
      |                                                  ^
a.cc:152:42: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  152 |                         for(register int i=0;i<=sum;++i)
      |                                          ^
a.cc:155:50: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  155 |                                 for(register int j=1;j<=pv+1;++j)d[j][0]=cnt[j][0],d[j][1]=cnt[j][1];
      |                                                  ^
a.cc:157:50: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  157 |                                 for(register int j=1;j<pv;++j)
      |                                                  ^
a.cc:168:42: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  168 |                         for(register int i=0;i<=sum;++i)
      |                                          ^
a.cc:171:50: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  171 |                                 for(register int j=1;j<=pv;++j)d[j][0]=cnt[j][0],d[j][1]=cnt[j][1];
      |                                                  ^
a.cc:173:50: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  173 |                                 for(register int j=pv;j>1;--j)
      |                                                  ^
a.cc:184:42: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  184 |                         for(register int i=0;i<=sum;++i)
      |                                          ^
a.cc:187:50: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  187 |                                 for(register int j=1;j<=pv;++j)d[j][0]=cnt[j][0],d[j][1]=cnt[j][1];
      |                                                  ^
a.cc:189:50: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  189 |                                 for(register int j=pv;j>1;--j)
      |                                                  ^