# Bzoj3706 反色刷

Posted by yjjr's blog on February 6, 2018

Description

1 x

2

Input

Output

Sample Input

6 6

1 2 1

2 3 1

1 3 1

4 5 1

5 6 1

4 6 1

14

2

1 0

2

1 1

1 2

2

1 3

1 4

1 5

2

1 3

1 4

1 5

2

Sample Output

2

-1

1

0

1

HINT

100%  n,m,q <= 1000000, c < 2，没有重边自环

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
using namespace std;
{
LL f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e6+6;
LL n,m,q,ans,cnt=0,r1,r2,x,y;
LL fa[maxn],u[maxn],v[maxn],c[maxn],d[maxn],sum[maxn];
inline LL find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main()
{
rep(i,1,n)fa[i]=i;
rep(i,1,m){
r1=find(u[i]),r2=find(v[i]);
if(r1!=r2){
fa[r1]=r2;
if(sum[r2]&&sum[r1])ans--;
sum[r2]+=sum[r1];
}
if(c[i]){
sum[r2]++;
if(sum[r2]==1)ans++;
d[u[i]]++,d[v[i]]++;
if(d[u[i]]&1)cnt++;else cnt--;
if(d[v[i]]&1)cnt++;else cnt--;
}
else if(r1!=r2&&sum[r1]&&sum[r2])ans--;
}
rep(i,1,q){
if(x==1){
c[y]^=1;r1=find(u[y]);
if(c[y]){
sum[r1]++;
if(sum[r1]==1)ans++;
d[u[y]]++,d[v[y]]++;
if(d[u[y]]&1)cnt++;else cnt--;
if(d[v[y]]&1)cnt++;else cnt--;
}
else{
sum[r1]--;if(sum[r1]==0)ans--;
d[u[y]]--,d[v[y]]--;
if(d[u[y]]&1)cnt++;else cnt--;
if(d[v[y]]&1)cnt++;else cnt--;
}
}
else{
if(cnt)cout<<"-1\n";
else printf("%lld\n",ans);
}
}
return 0;
}