//JUST UNDERSTANDED THE MAIN IDEA
#include <bits/stdc++.h>
using namespace std;
#define SZ 1234567
#define pb push_back
vector<int> adj[SZ];
int n,stage,ff[SZ],d[4],sz[SZ];
int gf(int x) {return ff[x]?ff[x]=gf(ff[x]):x;}
vector<int> ps;
void uni(int a,int b)
{
a=gf(a),b=gf(b);
if(a==b) ps.pb(a);
else ff[a]=b,sz[b]+=sz[a];
}
void Init(int N_)
{
n=N_; stage=0;
for(int i=1;i<=n;++i) sz[i]=1;
}
struct DS
{
int u,good=1;
int ff[SZ],deg[SZ];
int gf(int x) {return ff[x]?ff[x]=gf(ff[x]):x;}
void init(int t)
{
u=t;
}
void adde(int a,int b)
{
if(a==u||b==u) return;
good&=(++deg[a])<=2;
good&=(++deg[b])<=2;
a=gf(a),b=gf(b);
if(a==b) good=0;
else ff[a]=b;
}
int calc()
{return good;}
}S[4];
void rebuild(int t)
{
for(int i=0;i<3;++i) S[i].init(adj[t][i]);
S[3].init(t);
for(int i=1;i<=n;++i)
for(auto b:adj[i]) if(i<b)
for(int k=0;k<4;++k)
S[k].adde(i,b);
}
void Link(int x,int y)
{
++x,++y;
if(!stage){
adj[x].pb(y); adj[y].pb(x);
uni(x,y);
if(adj[y].size()>=3) swap(x,y);
if(adj[x].size()>=3)
stage=1, rebuild(x);
}
else{
for(int j=0;j<4;++j)
S[j].adde(x,y);
}
}
int CountCritical(){
if(!stage)
{
if(ps.size()>=2) return 0;
if(ps.size()==0) return n;
return sz[gf(ps[0])];
}
else
return S[0].calc()+S[1].calc()+S[2].calc()+S[3].calc();
}
