#include <vector>
using namespace std;
int n,focused=-1,ch[5],cnt,mx,deg[1000001],deg2[1000001],p[1000001][5],cycle,cyclesize,sz[1000001][5];
vector <int> candidates,ke[1000001];
vector <pair <int, int>> edge;
void reset(int j){
for (int i=0;i<n;i++){
p[i][j]=i;
sz[i][j]=1;
}
ch[j]=1;
}
int f(int i, int j){
return (p[i][j]==i?i:p[i][j]=f(p[i][j],j));
}
bool unite(int u, int v, int idx){
u=f(u,idx);
v=f(v,idx);
if (u==v)
return 0;
if (sz[u][idx]<sz[v][idx])
swap(u,v);
sz[u][idx]+=sz[v][idx];
p[v][idx]=u;
return 1;
}
void focus(int node, int j=0){
reset(j);
if (focused!=-1)
for (int i=0;i<n;i++)
deg[i]=0;
for (auto [u,v]:edge)
if (u!=node&&v!=node){
ch[j]&=unite(u,v,j);
if (focused!=-1){
deg[u]++;
deg[v]++;
if (max(u,v)>2)
ch[j]=0;
}
}
}
void Init(int N){
n=N;
for (int i=0;i<5;i++)
reset(i);
}
void Link(int a, int b){
edge.push_back({a,b});
if (focused!=-1){
if (a!=focused&&b!=focused){
ch[0]&=unite(a,b,0);
deg[a]++;
deg[b]++;
if (max(deg[a],deg[b])>2)
ch[0]=0;
}
return;
}
deg[a]++;
deg[b]++;
ke[a].push_back(b);
ke[b].push_back(a);
if (deg[a]==4){
focus(a);
focused=a;
return;
}
if (deg[b]==4){
focus(b);
focused=b;
return;
}
int cnt2=cnt;
if (deg[a]==3){
cnt2++;
for (int v:ke[a])
if (deg[v]>2&&v!=b){
deg2[a]++;
deg2[v]++;
}
}
if (deg[b]==3){
cnt2++;
for (int v:ke[b])
if (deg[v]>2){
deg2[b]++;
deg2[v]++;
}
}
if (cnt2>4){
cnt=cnt2;
return;
}
if (!cnt2){
if (deg[a]==2&°[b]==2&&f(a,0)==f(b,0)){
cycle++;
cyclesize=sz[f(a,0)][0];
}
unite(a,b,0);
}
else if (cnt2==1){
if (!cnt){
if (deg[a]<deg[b])
swap(a,b);
candidates.push_back(a);
for (int v:ke[a])
candidates.push_back(v);
for (int i=0;i<candidates.size();i++)
focus(candidates[i],i);
}
else{
for (int i=0;i<candidates.size();i++)
if (a!=candidates[i]&&b!=candidates[i])
ch[i]&=unite(a,b,i);
}
}
else if (cnt2==2){
if (cnt<2){
candidates.clear();
int u=-1,v=-1;
for (int i=0;i<n;i++)
if (deg[i]>2)
(u==-1?u=i:v=i);
for (int i=0;i<n;i++){
int cnt3=(i==u||i==v);
for (int j:ke[i])
cnt3+=(j==u||j==v);
if (cnt3==2)
candidates.push_back(i);
}
for (int i=0;i<candidates.size();i++)
focus(candidates[i],i);
}
else{
for (int i=0;i<candidates.size();i++)
if (a!=candidates[i]&&b!=candidates[i])
ch[i]&=unite(a,b,i);
}
}
else if (cnt<cnt2){
candidates.clear();
for (int i=0;i<n;i++)
if (deg[i]>2&°2[i]==cnt2-1)
candidates.push_back(i);
for (int i=0;i<candidates.size();i++)
focus(candidates[i],i);
}
else{
for (int i=0;i<candidates.size();i++)
if (a!=candidates[i]&&b!=candidates[i])
ch[i]&=unite(a,b,i);
}
cnt=cnt2;
}
int CountCritical(){
if (focused!=-1)
return ch[0];
if (cnt>4)
return 0;
if (cnt){
int res=0;
for (int i=0;i<candidates.size();i++)
res+=ch[i];
return res;
}
return (cycle>1?0:(cycle==1?cyclesize:n));
}
