#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,eq3;
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];
void specialul(int x)
{
speciale++;nodspecial[speciale]=x;
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;
}
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]==3)
{
gradmx=3;eq3++;
if(eq3>4) busit=1;
if(!speciale)
{
specialul(x);
for(int i=0;i<v[x].size();i++)
specialul(v[x][i]);
}
return;
}
else
{
gradmx=grad[x];
if(grad[x]>3)
{
if(speciale!=special[x])
{
speciale=0;
specialul(x);
}
}
}
}
}
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;
}
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(ret==0) busit=1;
return ret;
}
