#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000000;
int n;
vector<int> v[N];
int deg[N];
int bad=0;
int big[N]; //number of adjacent big nodes
int cnt[N+1]; //number of good nodes with i adjacent big nodes
int cntbad[N+1]; //number of bad nodes with i adjacent big nodes
vector<int> four;
int p[N];
int sz[N];
vector<array<int,2>> cycle_edges;
int incycle[N];
bool valid[N];
int find_set(int a)
{
if(a==p[a]) return a;
else return p[a]=find_set(p[a]);
}
bool merge_sets(int a,int b)
{
a=find_set(a);
b=find_set(b);
if(a==b) return 0;
if(sz[a]<sz[b]) swap(a,b);
p[b]=a;
sz[a]+=sz[b];
return 1;
}
vector<int> find_path(int a,int b)
{
vector<int> u(n,-1);
u[a]=-2;
queue<int> q;
q.push(a);
while(!q.empty())
{
int e=q.front();
q.pop();
for(int to:v[e])
{
if(u[to]==-1)
{
u[to]=e;
q.push(to);
}
}
}
vector<int> path={b};
while(path.back()!=a) path.push_back(u[path.back()]);
for(int x:path) incycle[x]++;
return path;
}
void Init(int _n)
{
n=_n;
cnt[0]=n;
for(int i=0;i<n;i++)
{
p[i]=i;
sz[i]=1;
valid[i]=1;
}
}
void upd(int a,int d)
{
if(valid[a]) (deg[a]<=2?cnt[big[a]]:cntbad[big[a]])+=d;
}
void updbig(int a)
{
upd(a,-1);
big[a]++;
upd(a,1);
}
void upddeg(int a)
{
upd(a,-1);
deg[a]++;
upd(a,1);
if(deg[a]==3)
{
bad++;
for(int to:v[a]) updbig(to);
}
if(deg[a]==4) four.push_back(a);
}
void new_valid(vector<int> opt)
{
vector<int> now(n,0);
for(int a:opt) now[a]=1;
for(int i=0;i<n;i++)
{
if(valid[i]&&!now[i])
{
upd(i,-1);
valid[i]=0;
}
}
}
void Link(int a, int b)
{
if(merge_sets(a,b)==1)
{
v[a].push_back(b);
v[b].push_back(a);
}
else
{
cycle_edges.push_back({a,b});
vector<int> path=find_path(a,b);
if(cycle_edges.size()==1) new_valid(path);
else if(cycle_edges.size()==2)
{
vector<int> opt;
for(int x:path)
{
int c=0;
for(int to:v[x]) c+=(incycle[to]==2);
if(incycle[x]==2&&c<=1) opt.push_back(x);
}
new_valid(opt);
}
}
upddeg(a);
upddeg(b);
}
int CountCritical()
{
if(four.size()==0) return cnt[bad]+cntbad[bad-1];
else if(four.size()==1) return (valid[four[0]]&&big[four[0]]==bad-1);
else return 0;
}
