int N;
const int MN = 1000010;
struct str{
int p[MN],r[MN];
int deg[MN];
int px;
bool ch;
void init(int x){
int i;
for(i=0;i<N;i++){deg[i]=0,p[i]=i,r[i]=1;}
px=x,ch=true;
}
int Find(int x){
while(x!=p[x])x=p[x];
return x;
}
bool Union(int x,int y){
deg[x]++,deg[y]++;
int a=Find(x),b=Find(y);
if(a==b)return true;
if(r[a]>r[b]){p[b]=a,r[a]+=r[b],r[b]=0;}
else{p[a]=b,r[b]+=r[a],r[a]=0;}
return false;
}
}ring[5];
int ans;
int cnt;
bool flag_3;
bool flag_cycle;
int st[MN],en[MN<<1],next[MN<<1];
int in[MN][2];
void addedge(int s,int d,int c)
{
next[c]=st[s];
st[s]=c;
en[c]=d;
}
void Init(int N_){
ans = N = N_;
ring[0].init(0);
}
void make_ring(int arr[])
{
int i,j;
for(i=0;i<4;i++){
ring[i].init(arr[i]);
for(j=1;j<=cnt;j++){
if(in[j][0]==arr[i]||in[j][1]==arr[i])continue;
if(ring[i].Union(in[j][0],in[j][1]))ring[i].ch=false;
if(ring[i].deg[in[j][0]]>=3 || ring[i].deg[in[j][1]]>=3)ring[i].ch=false;
}
}
}
void Link(int A, int B){
cnt++;
addedge(A,B,2*cnt);
addedge(B,A,2*cnt+1);
in[cnt][0]=A,in[cnt][1]=B;
if(flag_3){
int i;
for(i=0;i<4;i++){
if(A!=ring[i].px && B!=ring[i].px){
if(ring[i].Union(A,B))ring[i].ch=false;
if(ring[i].deg[A]>=3 || ring[i].deg[B]>=3)ring[i].ch=false;
}
}
return;
}
if(ring[0].Union(A,B)){
if(flag_cycle)ans=0;
else{
int ta=ring[0].Find(A);
ans=ring[0].r[ta];
flag_cycle=1;
}
}
if(ring[0].deg[A]>=3){
int arr[5]={A};
int i,tmp=1;
for(i=st[A];i;i=next[i]){
arr[tmp++]=en[i];
}
make_ring(arr);
flag_3 = true;
}
else if(ring[0].deg[B]>=3){
int arr[5]={B};
int i,tmp=1;
for(i=st[B];i;i=next[i]){
arr[tmp++]=en[i];
}
make_ring(arr);
flag_3 = true;
}
}
int CountCritical(){
if(flag_3){
int i,ret=0;
for(i=0;i<4;i++){
if(ring[i].ch)ret++;
}
return ret;
}
return ans;
}
