#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > e;
struct graph
{
int v,par[1000005],deg[1000005],sz[1000005],cyc,csz;
pair<int,int> mx;
graph()
{
v=-1;
cyc=0;
mx={0,0};
for (int i=0;i<1e6;i++)
{
par[i]=i;
deg[i]=0;
sz[i]=1;
}
}
int find(int x)
{
if (par[x]!=x)
par[x]=find(par[x]);
return par[x];
}
void Union(int x,int y)
{
deg[x]++;
deg[y]++;
mx=max(mx,{deg[x],x});
mx=max(mx,{deg[y],y});
x=find(x);
y=find(y);
if (x==y)
{
cyc++;
csz=sz[x];
}
else
{
par[x]=y;
sz[y]+=sz[x];
}
}
};
int n;
graph g[5];
bool f;
void Init(int nn)
{
n=nn;
}
void Link(int a,int b)
{
e.push_back({a,b});
if (!f)
{
g[0].Union(a,b);
if (g[0].mx.first==3)
{
f=1;
vector<int> cur({g[0].mx.second});
for (auto p:e)
{
if (p.first==cur[0] || p.second==cur[0])
cur.push_back(p.first^p.second^cur[0]);
}
for (int i=0;i<4;i++)
{
g[i+1].v=cur[i];
for (auto p:e)
{
if (p.first!=cur[i] && p.second!=cur[i])
g[i+1].Union(p.first,p.second);
}
}
}
}
else
{
for (int i=1;i<5;i++)
{
if (g[i].v!=a && g[i].v!=b)
g[i].Union(a,b);
}
}
}
int CountCritical()
{
if (!f)
{
if (!g[0].cyc)
return n;
if (g[0].cyc>1)
return 0;
return g[0].csz;
}
int ans=0;
for (int i=1;i<5;i++)
ans+=(g[i].mx.first<=2 && !g[i].cyc);
return ans;
}
