stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

#include <vector>



using namespace std;

 

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)

#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)

#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)

#define all(c) (c).begin(),(c).end()

#define sz(v) (int)(v).size()



typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;

const ll mod = 1e9+7;



void dbg(){ cerr << "\n"; }  

template <typename T,typename ...T2>

void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }









int main()

{

 

	//cin.tie(0); ios_base::sync_with_stdio(false);

	int n, c;

	cin >> n >>c;

	vector<vector<pii>> dt(c);

	

	rep(i, n){

		int s,t,z;

		cin >>s >>t >>z;

		dt[z-1].emplace_back(2*s-1, 2*t);

	}

	rep(i, c) sort(all(dt[i]));

	

	rep(i, c) if(sz(dt[i])>0){

		vector<pii> vp ={ dt[i][0] };

		rep2(j, 1, sz(dt[i])){

			if(vp.back().second >= dt[i][j].first){

				vp.back().second = dt[i][j].second;

			}else vp.push_back(dt[i][j]);

		}

		dt[i] = vp;

	}

	

	const int MXS=200100;

	vector<int> tm(MXS+100);

	rep(i, c) for(auto z: dt[i]){

		tm[z.first]++; tm[z.second + 1]--;

	}

	rep(i, MXS) tm[i+1] += tm[i];

	int ans =0;

	rep(i, MXS) ans = max(ans, tm[i]);

	cout << ans <<"\n";

	

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.2127468270331367x):
#include <bits/stdc++.h>





#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)

#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)

#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)

#define all(c) (c).begin(),(c).end()

#define sz(v) (int)(v).size()



using namespace std;

typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;

const int MD = (int)1e9 + 7; typedef vector<ll> VL;

void dbg(){ cerr << "\n"; }  template <class T, class ...T2>

void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

template <class T, class T2> void amax(T& a,T2 b){ if(a < b) a = b;}



int main()

{

	cin.tie(0); ios_base::sync_with_stdio(false);

	int n, c;

	cin >>n >>c;

	vector<VI> dt(n, VI(4)), dt2; 

	rep(i, n) cin >>dt[i][1] >>dt[i][2] >>dt[i][0];

	sort(all(dt));

	VI ccr = dt[0];

	rep2(i, 1, n){

		if(ccr[0] == dt[i][0] && ccr[2]==dt[i][1]){

			ccr[2] = dt[i][2];

		}else{

			dt2.push_back(ccr);

			ccr = dt[i];

		}

	}

	dt2.push_back(ccr);

	sort(all(dt2), [](auto& l, auto& r){return l[1] < r[1];});

	VI vdr; int ans = 0;

	for(const auto& x: dt2){

		int add = 1;

		for(auto& z: vdr){

			if( z < x[1]){

				z = x[2]; add = 0; break;

			}

		}

		if(add==1){

			vdr.push_back(x[2]);

			ans = max(ans, sz(vdr));

		}

	}

	cout <<ans <<"\n";

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;

const int MAXN=100001;

int n,m,st[MAXN],et[MAXN],c[MAXN],pre[2*MAXN],res[2*MAXN];



int main()

{

	cin >> n >> m;

	for(int i=1;i<=n;i++) cin >>st[i] >>et[i] >>c[i];

	for(int i=1;i<=m;i++)

	{

		memset(pre,0,sizeof(pre));

		for(int j=1;j<=n;j++) if(c[j]==i) pre[st[j]*2-1]++,pre[et[j]*2]--;

		for(int j=1;j<=2*MAXN-2;j++) pre[j]+=pre[j-1];

		for(int j=1;j<=2*MAXN-2;j++) if(pre[j]>0) res[j]++;

	}

	

	int ans=0;

	for(int i=1;i<=2*MAXN-2;i++) ans=max(ans,res[i]);

	cout << ans;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3060284337560137x):
#include <bits/stdc++.h>



using namespace std;

const int MAXN=100001;

int n,m,st[MAXN],et[MAXN],c[MAXN],pre[2*MAXN],res[2*MAXN];



int main()

{

	cin >> n >> m;

	for(int i=1;i<=n;i++) cin >>st[i] >>et[i] >>c[i];

	for(int i=1;i<=m;i++)

	{

		memset(pre,0,sizeof(pre));

		for(int j=1;j<=n;j++) if(c[j]==i) pre[st[j]]++,pre[et[j]+1]--;

		for(int j=1;j<=MAXN;j++) pre[j]+=pre[j-1];

		for(int j=1;j<=MAXN;j++) if(pre[j]>0) res[j]++;

	}

	

	int ans=0;

	for(int i=1;i<=2*MAXN-2;i++) ans=max(ans,res[i]);

	cout << ans;

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;

const int MAXN=100001;

int n,m,st[MAXN],et[MAXN],c[MAXN],pre[2*MAXN],res[2*MAXN];



int main()

{

	cin >> n >> m;

	for(int i=1;i<=n;i++) cin >>st[i] >>et[i] >>c[i];

	for(int i=1;i<=m;i++)

	{

		memset(pre,0,sizeof(pre));

		for(int j=1;j<=n;j++) if(c[j]==i) pre[st[j]*2-1]++,pre[et[j]*2]--;

		for(int j=1;j<=2*MAXN-2;j++) pre[j]+=pre[j-1];

		for(int j=1;j<=2*MAXN-2;j++) if(pre[j]>0) res[j]++;

	}

	

	int ans=0;

	for(int i=1;i<=2*MAXN-2;i++) ans=max(ans,res[i]);

	cout << ans;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.6482522553153878x):
#include <bits/stdc++.h>



using namespace std;

const int MAXN=100001;

int n,m,st[MAXN],et[MAXN],c[MAXN],pre[MAXN],res[MAXN];



int main()

{

	cin >> n >> m;

	for(int i=1;i<=n;i++) cin >>st[i] >>et[i] >>c[i];

	for(int i=1;i<=m;i++)

	{

		memset(pre,0,sizeof(pre));

		for(int j=1;j<=n;j++) if(c[j]==i) pre[st[j]]++,pre[et[j]+1]--;

		for(int j=1;j<MAXN;j++) pre[j]+=pre[j-1];

		for(int j=1;j<MAXN;j++) if(pre[j]>0) res[j]++; //因为i,j属于一个频道，所以只能算一次 

	}

	

	int ans=0;

	for(int i=1;i<MAXN;i++) ans=max(ans,res[i]);

	cout << ans;

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;

const int MAXN=100001;

int n,m,st[MAXN],et[MAXN],c[MAXN],pre[2*MAXN],res[2*MAXN];



int main()

{

	cin >> n >> m;

	for(int i=1;i<=n;i++) cin >>st[i] >>et[i] >>c[i];

	for(int i=1;i<=m;i++)

	{

		memset(pre,0,sizeof(pre));

		for(int j=1;j<=n;j++) if(c[j]==i) pre[st[j]]++,pre[et[j]+1]--;

		for(int j=1;j<=MAXN;j++) pre[j]+=pre[j-1];

		for(int j=1;j<=MAXN;j++) if(pre[j]>0) res[j]++;

	}

	

	int ans=0;

	for(int i=1;i<=2*MAXN-2;i++) ans=max(ans,res[i]);

	cout << ans;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2620339746931624x):
#include <bits/stdc++.h>



using namespace std;

const int MAXN=100001;

int n,m,st[MAXN],et[MAXN],c[MAXN],pre[MAXN],res[MAXN];



int main()

{

	cin >> n >> m;

	for(int i=1;i<=n;i++) cin >>st[i] >>et[i] >>c[i];

	for(int i=1;i<=m;i++)

	{

		memset(pre,0,sizeof(pre));

		for(int j=1;j<=n;j++) if(c[j]==i) pre[st[j]]++,pre[et[j]+1]--;

		for(int j=1;j<MAXN;j++) pre[j]+=pre[j-1];

		for(int j=1;j<MAXN;j++) if(pre[j]>0) res[j]++; //因为i,j属于一个频道，所以只能算一次 

	}

	

	int ans=0;

	for(int i=1;i<MAXN;i++) ans=max(ans,res[i]);

	cout << ans;

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

using ll=long long;

const ll MOD=(ll)1e9+7;



int main(){

    int N,C; cin>>N>>C;

    vector<vector<bool>> used(C,vector<bool>(200011,false));

    for (int i = 0; i < N; ++i) {

        int s,t,c;

        cin>>s>>t>>c;

        s=s*2-1; t*=2; c--;

        for(;s<=t;s++){

            used[c][s]=true;

        }

    }



    int ans=0;

    for (int i = 0; i < 200005; ++i) {

        int cnt=0;

        for (int j = 0; j < C; ++j) {

            if(used[j][i]) cnt++;

        }

        ans=max(ans,cnt);

    }



    cout<<ans<<endl;



    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.4301370446235955x):
#include <bits/stdc++.h>

using namespace std;

using ll=long long;

const ll MOD=(ll)1e9+7;

//const ll MOD=(ll)998244353;

const ll INF=(ll)1e18+10;

const double PI = 2.0*acos(0);

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

int dy[]={-1,1,0,0};

int dx[]={0,0,-1,1};



void solve(int ca){

    int N,C; cin>>N>>C;

    vector<vector<bool>> used(C,vector<bool>(100010,false));

    int s,t,c;

    for (int i = 0; i < N; ++i) {

        cin>>s>>t>>c; --s; --c;

        for (int j = s; j < t; ++j) {

            used[c][j]=true;

        }

    }



    int ans=0;

    for (int i = 0; i <= 100000; ++i) {

        int cnt=0;

        for (int j = 0; j < C; ++j) {

            if(used[j][i]) cnt++;

        }

        //if(cnt==3) cout<<i<<endl;

        chmax(ans,cnt);

    }

    cout<<ans<<endl;



}



//#define MULTI

int main() {

#ifdef MULTI

    int N; cin>>N;

    for (int i = 0; i < N; ++i) {

        solve(i+1);

    }

#else

    solve(0);

#endif

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

#include<cmath>

#include<string>

#include<cstdlib>



#define FOR(i,a,b) for(int i=(a);i<(b);++i)

#define REP(i,n)   FOR(i,0,n)

#define MOD 1000000007



using namespace std;

 

typedef long long int ll;



const ll INF=(ll)1e18;



int N,C;



int main(){

    cin >> N >> C;



    vector<pair<int, int> > st[31],st2[31];



    REP(i,N){

        int ss,tt,cc;

        cin >> ss >> tt >> cc;

        st[cc].push_back(make_pair(ss,tt));

    }

    FOR(i,1,C+1){

        sort(st[i].begin(),st[i].end());

    }

    FOR(i,1,C+1){

        int ss = -1;

        int tt = -1;

        REP(j,st[i].size()){

            if(ss == -1)ss=st[i][j].first;

            if(tt == -1){

                tt=st[i][j].second;

            }else{

                if(tt == st[i][j].first){

                    tt=st[i][j].second;

                }else{

                    st2[i].push_back(make_pair(ss,tt));

                    ss=st[i][j].first;

                    tt=st[i][j].second;

                }

            }

        }

        if(ss != -1)st2[i].push_back(make_pair(ss,tt));

    }



    // FOR(i,1,C+1){

    //     REP(j,st[i].size()){

    //         cout << st[i][j].first << " " << st[i][j].second << endl;

    //     }

    // }

    // FOR(i,1,C+1){

    //     REP(j,st2[i].size()){

    //         cout << st2[i][j].first << "  " << st2[i][j].second << endl;

    //     }

    // }



    int rec[300000] = {0};

//    FOR(i,300001)rec[i] = 0;



    FOR(i,1,C+1){

        REP(j,st2[i].size()){

            rec[st2[i][j].first * 2 - 1] += 1;

            rec[st2[i][j].second * 2] -= 1;

        }

    }



    // REP(i,30){

    //     cout << i << " " << rec[i] << endl;

    // }

    int ans = 0;

    REP(i,300000-1){

        rec[i+1] = rec[i+1] + rec[i];

        ans = max(ans, rec[i+1]);

    }



    // REP(i,30){

    //     cout << i << " " << rec[i] << endl;

    // }

    cout << ans << endl;



}

// Faster C++ solution for the same problem (measured speedup: 1.3102580362720486x):
#include <bits/stdc++.h>

using namespace std;



#define FOR(i,a,b) for(int i=(a);i<(b);++i)

#define REP(i,n)   FOR(i,0,n)

#define ALL(a)     (a).begin(),(a).end()

#define MOD 1000000007



typedef long long int ll;



const ll INF=(ll)1e19;

//const int INF=(1<<30);







int main(){

  int N,C;

  cin >> N >> C;



  vector<vector<pair<int, int>>> st(C+1);



  REP(i,N){

    int s,t,c;

    cin >> s >> t>> c;

    st[c].push_back(make_pair(s,t));

  }



  vector<int> sum(200001,0);



  FOR(i,1,C+1){

    sort(ALL(st[i]));

    REP(j,st[i].size()){

      if(j>0 && st[i][j-1].second == st[i][j].first){

        sum[st[i][j].first*2+1] += 1;

        sum[st[i][j].second*2+1] -= 1;        

      }else{

        sum[st[i][j].first*2-1] += 1;

        sum[st[i][j].second*2+1] -= 1;        

      }

    }



  }



  FOR(i,1,sum.size()){

    sum[i] += sum[i-1];

  }



  int ans=0;

  FOR(i,1,sum.size()){

    ans = max(ans,sum[i]);

  }

  cout << ans << endl;

}
// Slower C++ solution:
// luogu-judger-enable-o2

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cctype>

using namespace std;

inline int read(int f = 1, int x = 0, char ch = ' ')

{

    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;

    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();

    return f*x;

}

const int N = 1e5+5;

struct Edge

{

    int next, to;

    Edge(int next = 0, int to = 0):next(next), to(to) {};

}edge[N<<1];

int tot, head[N];

void _add(int x, int y) { edge[++tot] = Edge(head[x], y); head[x] = tot; }

void add(int x, int y) { _add(x, y); _add(y, x); }

int n, m, cn, w[N], f[N], fa[N], s[N], p, q, ans;

int find(int x) { return f[x] == x?x:f[x] = find(f[x]); }

void dfs(int x, int f, int c)

{

    fa[x] = f, s[x] = c;

    for(int i = head[x]; i; i = edge[i].next)

    {

        int y = edge[i].to; if(y == f) continue;

        dfs(y, x, -c); s[x] += s[y];

    }

}

int main()

{

    n = read(), m = read(), p = 1;

    for(int x = 1; x <= n; ++x) f[x] = x;

    for(int i = 1; i <= m; ++i)

    {

        int x = read(), y = read();

        if(find(x) == find(y)) p = x, q = y;

        else f[find(y)] = find(x), add(x, y);

    }

    dfs(p, 0, 1);

    if(n == m)

    {

        for(int x = q; x; x = fa[x]) w[++cn] = s[x];

        if(cn&1)

        {

            if(s[p]&1) return puts("-1"), 0;

            for(int x = q; x; x = fa[x]) s[x] -= s[p]>>1;

        } 

        else

        {

            if(s[p]) return puts("-1"), 0;

            sort(w+1, w+1+cn);   

            for(int x = q; x; x = fa[x]) s[x] -= w[cn>>1];

        }

    }

    else if(s[p]) return puts("-1"), 0;

    for(int x = 1; x <= n; ++x) ans += abs(s[x]);

    printf("%d\n", ans);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.803548880103423x):
#include<bits/stdc++.h>

using namespace std;

#define N 200010

int n,m,a[N],v[N],nxt[N],h[N],ec,hx,hy,p[N],f[N],st[N],tp;

int fd(int x){return p[x]==x?x:p[x]=fd(p[x]);}

void add(int x,int y){v[++ec]=y;nxt[ec]=h[x];h[x]=ec;}

void dfs(int x,int fa,int va){

	a[x]=va;

	for(int i=h[x];i;i=nxt[i])

		if(v[i]!=fa){

			f[v[i]]=x;

			dfs(v[i],x,-va);

			a[x]+=a[v[i]];

		}

}

int main(){

	cin>>n>>m;

	for(int i=1;i<=n;i++)p[i]=i;

	hx=hy=1;

	for(int i=1;i<=m;i++){

		int x,y;

		cin>>x>>y;

		if(fd(x)!=fd(y))p[fd(x)]=fd(y);

		else{

			hx=x;

			hy=y;

			continue;

		}

		add(x,y);add(y,x);

	}

	dfs(hx,0,-1);

	if(n==m){

		for(int i=hy;i;i=f[i])

			st[++tp]=a[i];

		if(tp&1){

			if(a[hx]&1){

				puts("-1");

				return 0;

			}

			for(int i=hy;i;i=f[i])

				a[i]-=a[hx]/2;

		}

		else{

			if(a[hx]){

				puts("-1");

				return 0;

			}

			sort(st+1,st+tp+1);

			for(int i=hy;i;i=f[i])

				a[i]-=st[tp/2];

		}

	}

	else if(a[1]){

		puts("-1");

		return 0;

	}

	int r=0;

	for(int i=1;i<=n;i++)r+=abs(a[i]);

	cout<<r;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define N 100005

#define ll long long

#define NoSolution return puts("-1"),0 

#define For(i,x,y) for(int i=(x);i<=(y);++i)

#define Rof(i,x,y) for(int i=(x);i>=(y);--i)

#define Edge(x) for(int i=head[x];i;i=e[i].nxt)

#define mset(x,y) memset(x,y,sizeof(x))

#define p_b push_back 

using namespace std;



int f[N],fa[N],dep[N],cnt=0,b[N],_u,_v;

vector<int> g[N];



void dfs(int x,int v){

	f[x]=v;

	for(auto to:g[x]){

		if(!dep[to]){

			fa[to]=x,dep[to]=dep[x]+1;

			dfs(to,-v);

			f[x]+=f[to];

		} else if(to!=fa[x]){

			_u=x,_v=to;

		}

	}

}

int main(){

	int n,m,u,v,ans=INT_MAX,mid,tmp,cnt;

	dep[1]=1;

	scanf("%d%d",&n,&m);

	For(i,1,m){

		scanf("%d%d",&u,&v);

		g[u].p_b(v),g[v].p_b(u);

	}

	dfs(1,1);

	if(m==n-1){

		ans=0;

		if(f[1]) NoSolution;

		For(i,1,n) ans+=abs(f[i]);

		printf("%d\n",ans);

	} else{

		if((dep[_v]-dep[_u]+1)%2==0){

			if(f[1]) NoSolution;

			tmp=0,cnt=0;

			For(i,1,n) tmp+=abs(f[i]);

			ans=min(ans,tmp);

			for(int i=_v;i!=_u;i=fa[i]) tmp-=abs(f[i]),b[++cnt]=f[i];

			sort(b+1,b+cnt+1);

			cnt&1?mid=b[(cnt+1)/2]:mid=(b[cnt/2]+b[cnt/2+1])/2;

			tmp+=abs(mid);

			for(int i=_v;i!=_u;i=fa[i]) tmp+=abs(f[i]-mid);

			ans=min(ans,tmp);

			printf("%d\n",ans);		

		} else{

			if(f[1]%2) NoSolution;

			int tmp=f[1]/2;ans=abs(tmp);

			for(int i=_u;i;i=fa[i]) f[i]-=tmp;

			for(int i=_v;i;i=fa[i]) f[i]-=tmp;

			For(i,1,n) ans+=abs(f[i]);

			printf("%d\n",ans);

		}

	}

}

// Faster C++ solution for the same problem (measured speedup: 3.540605369512264x):
#include<bits/stdc++.h>

using namespace std;

#define N 200010

int n,m,a[N],v[N],nxt[N],h[N],ec,hx,hy,p[N],f[N],st[N],tp;

int fd(int x){return p[x]==x?x:p[x]=fd(p[x]);}

void add(int x,int y){v[++ec]=y;nxt[ec]=h[x];h[x]=ec;}

void dfs(int x,int fa,int va){

	a[x]=va;

	for(int i=h[x];i;i=nxt[i])

		if(v[i]!=fa){

			f[v[i]]=x;

			dfs(v[i],x,-va);

			a[x]+=a[v[i]];

		}

}

int main(){

	cin>>n>>m;

	for(int i=1;i<=n;i++)p[i]=i;

	hx=hy=1;

	for(int i=1;i<=m;i++){

		int x,y;

		cin>>x>>y;

		if(fd(x)!=fd(y))p[fd(x)]=fd(y);

		else{

			hx=x;

			hy=y;

			continue;

		}

		add(x,y);add(y,x);

	}

	dfs(hx,0,-1);

	if(n==m){

		for(int i=hy;i;i=f[i])

			st[++tp]=a[i];

		if(tp&1){

			if(a[hx]&1){

				puts("-1");

				return 0;

			}

			for(int i=hy;i;i=f[i])

				a[i]-=a[hx]/2;

		}

		else{

			if(a[hx]){

				puts("-1");

				return 0;

			}

			sort(st+1,st+tp+1);

			for(int i=hy;i;i=f[i])

				a[i]-=st[tp/2];

		}

	}

	else if(a[1]){

		puts("-1");

		return 0;

	}

	int r=0;

	for(int i=1;i<=n;i++)r+=abs(a[i]);

	cout<<r;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(int i=(a),_ed=(b);i<=_ed;++i)

#define DREP(i,a,b) for(int i=(a),_ed=(b);i>=_ed;--i)

#define pb(x) push_back((x))

typedef long long ll;

inline int read(){

    register int x=0,f=1;register char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}

    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}

    return f?x:-x;

}



const int N=1e5+5;

int n,m,dep[N],s,t,flg,S[N],k[N],stk[N],tp;

ll ans;

vector<int> E[N];



inline void Dfs(int u,int pa){

    for(int v:E[u]){

	if(v==pa)continue;

	if(dep[v]){flg=(dep[u]==dep[v]);s=u,t=v;continue;}

	dep[v]=dep[u]*-1;Dfs(v,u);

    }

}

inline void Cal(int u,int pa){

    for(int v:E[u]){

	if(v==pa||(u==s&&v==t)||(v==s&&u==t))continue;

	Cal(v,u);

	S[u]+=S[v];k[u]+=k[v];

    }

}



int main(){

    //freopen("in.in","r",stdin);

    n=read(),m=read();

    REP(i,1,m){int u=read(),v=read();E[u].pb(v),E[v].pb(u);}

    dep[1]=1;Dfs(1,0);

    int sum=0;

    REP(i,1,n)sum+=(S[i]=dep[i]);

    if(m==n-1){if(sum)return puts("-1"),0;}

    else if((flg&&(sum&1))||(!flg&&sum))return puts("-1"),0;

    if(m==n){

	if(flg){

	    S[s]-=sum/2,S[t]-=sum/2;

	    ans+=abs(sum/2);

	}

	else k[s]=1,k[t]=-1;

    }

    Cal(1,0);

    REP(i,1,n)

	if(!k[i])ans+=abs(S[i]);

	else if(~k[i])stk[++tp]=-S[i];

	else stk[++tp]=S[i];

    stk[++tp]=0;

    sort(stk+1,stk+tp+1);

    int x=stk[(tp+1)>>1];

    REP(i,1,tp)ans+=abs(stk[i]-x);

    printf("%lld\n",ans);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.576766860833536x):
//code from https://www.luogu.com.cn/blog/flashblog/solution-at2046

#include<bits/stdc++.h>

#define R register int

#define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin))

using namespace std;

const int SZ=1<<19,N=1e5+9,M=2*N;

char buf[SZ],*ie=buf+SZ,*ip=ie-1;

inline int in(){

    G;while(*ip<'-')G;

    R x=*ip&15;G;

    while(*ip>'-'){x*=10;x+=*ip&15;G;}

    return x;

}

int he[N],ne[M],to[M],f[N],a[N],b[N];

int Getf(R x){

    return x==f[x]?x:f[x]=Getf(f[x]);

}

void Dfs(R x,R op){

    a[x]=op;

    for(R y,i=he[x];i;i=ne[i])

        if((y=to[i])!=f[x])

            f[y]=x,Dfs(y,-op),a[x]+=a[y];

}

int main(){

    R n=in(),m=in(),rt=1,re=1,p=0,ans=0;

    for(R i=1;i<=n;++i)f[i]=i;

    for(R p=0,i=1;i<=m;++i){

        R x=in(),y=in();

        if(Getf(x)!=Getf(y))f[f[x]]=f[y];

        else{rt=x,re=y;continue;}//把多的边单独拿出来

        ne[++p]=he[x];to[he[x]=p]=y;

        ne[++p]=he[y];to[he[y]=p]=x;

    }

    f[rt]=0;Dfs(rt,1);

    if(n==m){//基环树

        for(R x=re;x;x=f[x])b[++p]=a[x];

        if(p&1){//奇环

            if(a[rt]&1)return puts("-1"),0;

            for(R x=re;x;x=f[x])a[x]-=a[rt]>>1;

        }

        else{//偶环

            if(a[rt])return puts("-1"),0;

            sort(b+1,b+p+1);

            for(R x=re;x;x=f[x])a[x]-=b[p>>1];

        }

    }//树

    else if(a[rt])return puts("-1"),0;

    for(R i=1;i<=n;++i)ans+=abs(a[i]);

    return cout<<ans<<endl,0;

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<cmath>

using namespace std;



typedef long long ll;

const ll MAXN=1e5+5;



ll n,m,cir,spx,spy;

ll dis[MAXN],sum[MAXN],nx[MAXN];

ll sta[MAXN],top;

bool vis[MAXN];

vector<ll> E[MAXN];



void dfs(ll u,ll fa=0){

    vis[u]=1;

    dis[u]=dis[fa]+1;

    for(ll i=0;i<(ll)E[u].size();i++){

        ll v=E[u][i];

        if(v==fa) continue;

        if(vis[v]){

            cir=dis[u]-dis[v]+1;

            spx=u,spy=v;

            continue;

        }

        dfs(v,u);

    }

}



void solve(ll u,ll fa=0){

    vis[u]=1;

    for(ll i=0;i<(ll)E[u].size();i++){

        ll v=E[u][i];

        if(v==fa||vis[v]) continue;

        solve(v,u);

        nx[u]+=nx[v];

        sum[u]+=sum[v];

    }

}



int main(){

    //freopen("print.in","r",stdin);

    //freopen("print.out","w",stdout);



    scanf("%lld%lld",&n,&m);

    for(ll i=1;i<=m;i++){

        ll u,v;

        scanf("%lld%lld",&u,&v);

        E[u].push_back(v);

        E[v].push_back(u);

    }

    dis[0]=-1;

    dfs(1);

    ll tot=0,ans=0;

    for(ll i=1;i<=n;i++)

        tot+=(sum[i]=(dis[i]&1?-1:1));

    if(!cir){ if(tot) return puts("-1"),0;}

    else{

        if(cir&1){

            if(tot&1) return puts("-1"),0;

            sum[spx]-=tot/2;

            sum[spy]-=tot/2;

            ans+=abs(tot)/2;

        }

        else{

            if(tot) return puts("-1"),0;

            nx[spx]=1;

            nx[spy]=-1;

        }

    }

    memset(vis,0,sizeof vis);

    solve(1);

    for(ll i=1;i<=n;i++){

        if(!nx[i]) ans+=abs(sum[i]);

        else{

            if(nx[i]==1) sum[i]*=-1;

            sta[++top]=sum[i];

        }

    }

    sta[++top]=0;

    sort(sta+1,sta+top+1);

    ll k=sta[(top+1)/2];

    for(ll i=1;i<=top;i++)

        ans+=abs(sta[i]-k);

    printf("%lld\n",ans);



    fclose(stdin);

    fclose(stdout);

}


// Faster C++ solution for the same problem (measured speedup: 1.9298077599230834x):
#include<bits/stdc++.h>

using namespace std;

struct edge{int to,nxt;}e[200005];

int n,m,et,rx,rt,head[100005],fa[100005],a[100005],tot,b[100005],r;

inline void adde(int x,int y) {e[++tot]=(edge){y,head[x]},head[x]=tot;}

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

inline void dfs(int x,int fl,int f=0)

{

	a[x]=fl,fa[x]=f;

	for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=f) dfs(e[i].to,-fl,x),a[x]+=a[e[i].to];

}

int main()

{

	scanf("%d%d",&n,&m),et=0,rt=1,memset(head,0,sizeof(head));

	for(int i=1;i<=n;i++) fa[i]=i;

	for(int i=1,x,y;i<=m;i++) {scanf("%d%d",&x,&y);if(getf(x)!=getf(y)) adde(x,y),adde(y,x),fa[getf(x)]=getf(y);else rt=x,rx=y;}

	memset(a,0,sizeof(a)),fa[rt]=0,dfs(rt,1),tot=0,r=0;

	if(n!=m) {if(a[rt]) return puts("-1"),0;}

	else

	{

		for(int x=rx;x;x=fa[x]) b[++tot]=a[x];

		if(tot&1)

		{

			if(a[rt]&1) return puts("-1"),0;

			for(int x=rx;x;x=fa[x]) a[x]-=(a[rt]>>1);

		}

		else

		{

			if(a[rt]) return puts("-1"),0;

			sort(b+1,b+tot+1);

			for(int x=rx;x;x=fa[x]) a[x]-=b[tot>>1];

		}

	}

	for(int i=1;i<=n;i++) r+=abs(a[i]);

	return printf("%d\n",r),0;

}