#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],ab[10],abaux[10];
int maimari,busit,mme,gradmx,speciale,nr,auxi;
struct linker
{
int ciclu,wciclu,mxout;
char gr[nmax];
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(rg[A]>rg[B]) {tt[B]=A;rg[A]+=rg[B];}
else {tt[A]=B;rg[B]+=rg[A];}
}
void uneste(int x,int y)
{
gr[x]++;gr[y]++;
if(gr[x]>mxout) mxout=(int)gr[x];
if(gr[y]>mxout) mxout=(int)gr[y];
if(finds(x)==finds(y))
ciclu+=1,wciclu=rg[finds(x)];
else unite(finds(x),finds(y));
}
}li[6],aux[4];
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]++;
}
if(valid[x]!=speciale) return;
auxi++;
auxiliare[auxi]=x;
aux[auxi].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]==4)
{
maimari++;
if(maimari>1)
{
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)
{
ab[speciale]=0;
li[speciale].mxout=0;li[speciale].ciclu=0;li[speciale].wciclu=0;
li[speciale].ini();
for(int i=0;i<n;i++)
li[speciale].gr[i]=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;
}
}
if(gradmx==3&&speciale>4)
{
busit=1;
}
if(gradmx==3&&speciale==1)
{
for(int i=0;i<v[x].size();i++)
rezolva(v[x][i]);
}
}
void Init(int N_) {
n = N_;
li[0].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);
muchii[++nr]={A,B};
for(int i=(speciale!=0);i<=speciale;i++)
if((!ab[i]))
if(i==0||(nodspecial[i]!=A&&nodspecial[i]!=B))
li[i].uneste(A,B);
for(int i=1;i<=speciale;i++)
if(li[i].mxout>=3||li[i].ciclu)
ab[i]=1;
if(gradmx==3&&speciale<=2)
for(int i=1;i<=auxi;i++)
if(!abaux[i])
if(auxiliare[i]!=A&&auxiliare[i]!=B)
{
aux[i].uneste(A,B);
if(aux[i].mxout>2||aux[i].ciclu) abaux[i]=1;
}
}
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++;
else ab[i]=1;
}
if(gradmx==3&&speciale<=2)
{
for(int i=1;i<=auxi;i++)
if((!aux[i].ciclu)&&aux[i].mxout<3&&(!special[auxiliare[i]])) ret++;
else abaux[i]=1;
}
if(ret==0) busit=1;
return ret;
}
