Submission #74535909

---

Source Code Expand

#include<bits/stdc++.h>

// #define XAERIC666
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#ifndef XAERIC666
  #define xaeric(...) {fprintf(stderr,__VA_ARGS__);fflush(stderr);}
#else
  #define xaeric(...) 114514
#endif
int read(){
  int x=0,f=1;
  char c=getchar();
  while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
  while('0'<=c&&c<='9'){x=x*10+c-48;c=getchar();}
  return x*f;
}
// void in(int*a,int n){for(int i=1;i<=n;i++)a[i]=read();}
// void out(int*a,int n){for(int i=1;i<=n;i++)printf("%lld%c",a[i]," \n"[i==n]);}
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _rep(i,a,b) for(int i=(b);i>=(a);--i)
#define YES puts("YES");
#define NO puts("NO");
using namespace std;

const int P=998244353;
const int N=4e5+5;
int n,m;
int fa[N],c[N][2],ans;
int fd(int x){
  return fa[x]==x?x:fa[x]=fd(fa[x]);
}
void mrg(int x,int y){
  x=fd(x);
  y=fd(y);
  if(x!=y){
    ans-=min(c[x][0],c[x][1]);
    ans-=min(c[y][0],c[y][1]);
    c[y][0]+=c[x][0];
    c[y][1]+=c[x][1];
    ans+=min(c[y][0],c[y][1]);
    fa[x]=y;
  }
}

void solve(){
  n=read(),m=read();
  for(int i=1;i<=2*n;i++){
    fa[i]=i;
    if(i<=n){
      c[i][0]=1;
    }
    else{
      c[i][1]=1;
    }
  }
  bool f=0;
  for(int i=1;i<=m;i++){
    int u=read(),v=read();
    mrg(u,v+n);
    mrg(v,u+n);
    if(fd(u)==fd(u+n)){
      f=1;
    }
    if(fd(v)==fd(v+n)){
      f=1;
    }
    if(f){
      puts("-1");
    }
    else{
      printf("%lld\n",ans/2);
    }
  }  
}

signed main(){
  int TTTT=1;
  // int TTTT=read();
  while(TTTT--){
    solve();
  }
}

Submission Info

Judge Result