#include <iostream>
#include <vector>
using namespace std;
const int nmax=1000*1000+5;
int n;
pair<int,int> muchii[nmax];
vector<int> v[nmax];
int grad[nmax],special[nmax],valid[nmax];
int nodspecial[10],auxiliare[10];
int maimari,busit,mme,gradmx,speciale,nr,auxi;
struct dsu
{
int tt[nmax],rg[nmax];
void ini()
{
for(int i=0;i<n;i++)
tt[i]=i,rg[i]=1;
}
int finds(int x)
{
int y=x,aux=0;
while(x!=tt[x])
x=tt[x];
while(y!=x)
{
aux=tt[y];
tt[y]=x;
y=aux;
}
return x;
}
void unite(int A,int B)
{
if(A==B) return;
if(rg[A]>rg[B]) {tt[B]=A;rg[A]+=rg[B];}
else {tt[A]=B;rg[B]+=rg[A];}
}
};
struct linker
{
dsu dsu1;
int ciclu,wciclu,mxout,gr[nmax];
void uneste(int x,int y)
{
gr[x]++;gr[y]++;
if(gr[x]>mxout) mxout=gr[x];
if(gr[y]>mxout) mxout=gr[y];
if(dsu1.finds(x)==dsu1.finds(y))
ciclu+=1,wciclu=dsu1.rg[dsu1.finds(x)];
else dsu1.unite(dsu1.finds(x),dsu1.finds(y));
}
}li[7],aux[10];
void rezolva(int x)
{
if(grad[x]>=3||(valid[x])) return;
for(int i=0;i<v[x].size();i++)
if(grad[v[x][i]]==3)
{
valid[x]=1;
}
if(!valid[x]) return;
auxi++;
auxiliare[auxi]=x;
aux[auxi].dsu1.ini();
for(int i=1;i<=nr;i++)
if(muchii[i].first!=x&&muchii[i].second!=x)
aux[auxi].uneste(muchii[i].first,muchii[i].second);
}
void spec(int x)
{
if(grad[x]>3)
{
maimari++;
if(maimari>1)
{
busit=1;
return;
}
}
if(grad[x]>=3)
{
mme+=1;
if(mme>4)
{
busit=1;
return;
}
}
if(grad[x]>=gradmx&&grad[x]>=3)
{
if(grad[x]==gradmx)
{
speciale++;
}
else
{
speciale=1;
gradmx=grad[x];
}
nodspecial[speciale]=x;
if(special[x]!=speciale)
{
li[speciale].dsu1.ini();
li[speciale].mxout=0;
for(int i=1;i<=nr;i++)
if(muchii[i].first!=x&&muchii[i].second!=x)
li[speciale].uneste(muchii[i].first,muchii[i].second);
special[x]=speciale;
}
for(int it=speciale+1;it<9;it++)
special[nodspecial[it]]=0;
}
if(gradmx==3&&speciale<3)
{
for(int i=0;i<v[x].size();i++)
rezolva(v[x][i]);
}
}
void Init(int N_) {
n = N_;
li[0].dsu1.ini();
}
void Link(int A, int B) {
if(busit) return;
grad[A]++;
grad[B]++;
v[A].push_back(B);
v[B].push_back(A);
spec(A);
spec(B);
for(int i=0;i<=speciale;i++)
if(i==0||(nodspecial[i]!=A&&nodspecial[i]!=B))
li[i].uneste(A,B);
if(gradmx==3&&speciale<=2)
for(int i=1;i<=auxi;i++)
if(auxiliare[i]!=A&&auxiliare[i]!=B)
aux[i].uneste(A,B);
muchii[++nr]={A,B};
}
int CountCritical() {
if(busit)
{
return 0;
}
if(gradmx<3)
{
if(li[0].ciclu>1)
{
busit=1;
return 0;
}
if(li[0].ciclu==1)
return li[0].wciclu;
return n;
}
int ret=0;
for(int i=1;i<=speciale;i++)
{
if((!li[i].ciclu)&&li[i].mxout<3)
ret++;
}
if(gradmx==3&&speciale<=2)
{
for(int i=1;i<=auxi;i++)
if((!aux[i].ciclu)&&aux[i].mxout<3&&(!special[auxiliare[i]]))
ret++;
}
if(ret==0) busit=1;
return ret;
}
