#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define mp make_pair
#define pb push_back
const int N=1000050;
int n;
struct DSU
{
int p[N],c[N],deg[N];
int cyc,my,sz;
bool ok;
DSU(){}
void init(int x)
{
my=x;cyc=sz=0;ok=1;
for(int i=0;i<n;i++) p[i]=i,c[i]=1,deg[i]=0;
}
int Find(int x){ return x==p[x]?x:p[x]=Find(p[x]);}
void Union(int x, int y)
{
if(x==my || y==my) return;
deg[x]++;deg[y]++;
if(deg[x]>2 || deg[y]>2) ok=0;
x=Find(x);y=Find(y);
if(x==y){ cyc++,sz=c[x],ok=0;return;}
if(c[y]>c[x])
{
p[x]=y;
c[y]+=c[x];
}
else
{
p[y]=x;
c[x]+=c[y];
}
}
} Base,Try[4];
int E[N][3];
int esz;
pair<int,int> edges[N];
int deg[N],sz;
bool mod;
void Init(int m){ n=m;Base.init(-1);}
void Push()
{
for(int i=0;i<esz;i++)
{
for(int j=0;j<sz;j++)
{
Try[j].Union(edges[i].first,edges[i].second);
}
}
}
void Link(int a, int b)
{
if(deg[a]<3) E[a][deg[a]]=b;
deg[a]++;
if(deg[b]<3) E[b][deg[b]]=a;
deg[b]++;
Base.Union(a,b);
edges[esz++]=mp(a,b);
if(mod)
{
for(int i=0;i<sz;i++) Try[i].Union(a,b);
return;
}
if(deg[a]>2)
{
sz=4;
Try[0].init(a);
for(int i=0;i<3;i++) Try[i+1].init(E[a][i]);
Push();
mod=1;
return;
}
if(deg[b]>2)
{
sz=4;
Try[0].init(b);
for(int i=0;i<3;i++) Try[i+1].init(E[b][i]);
Push();
mod=1;
return;
}
}
int CountCritical()
{
if(mod)
{
int ans=0;
for(int i=0;i<sz;i++) if(Try[i].ok) ans++;
return ans;
}
if(Base.cyc>1) return 0;
if(Base.cyc==1) return Base.sz;
return n;
}
