#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000000;
int n;
vector<int> v[N];
vector<int> vc[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;
vector<array<int,2>> cycle_edges;
int incycle[N];
bool valid[N];
struct limiter;
vector<limiter> lim;
bool vis[N];
struct DSU
{
int p[N];
int sz[N];
DSU()
{
for(int i=0;i<N;i++)
{
p[i]=i;
sz[i]=1;
}
}
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;
}
}dsu;
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++) 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);
for(int to:vc[a]) updbig(to);
}
if(deg[a]==4) four.push_back(a);
}
void rm_valid(int a)
{
if(valid[a])
{
upd(a,-1);
valid[a]=0;
}
}
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]) rm_valid(i);
}
}
struct limiter
{
DSU d;
int id[N];
int root;
int tcnt=0;
limiter(int r)
{
memset(id,-1,sizeof(id));
root=r;
id[root]=-2;
dfs(root,-1);
}
void dfs(int a,int p)
{
if(a!=root)
{
if(p==root) id[a]=(tcnt++);
else id[a]=id[p];
}
for(int to:v[a]) if(to!=p) dfs(to,a);
}
bool inside(int a){return (id[a]!=-1);}
void add_subtree(int a,int b,vector<int> cc)
{
for(int x:cc) if(x==a) swap(a,b);
dfs(b,a);
}
void add_cycle(int a,int b)
{
if(a!=root&&b!=root&&d.merge_sets(id[a],id[b])==0) rm_valid(root);
}
};
vector<int> find_cc(int a)
{
vector<int> q;
auto add=[&](int x)
{
if(!vis[x])
{
q.push_back(x);
vis[x]=1;
}
};
add(a);
int idx=0;
while(idx<(int)q.size())
{
int e=q[idx++];
for(int to:v[e]) add(to);
}
for(int x:q) vis[x]=0;
return q;
}
void Link(int a, int b)
{
if(dsu.merge_sets(a,b)==1)
{
for(limiter &l:lim)
{
if(l.inside(a)) l.add_subtree(a,b,find_cc(b));
else if(l.inside(b)) l.add_subtree(a,b,find_cc(a));
}
v[a].push_back(b);
v[b].push_back(a);
}
else
{
vc[a].push_back(b);
vc[b].push_back(a);
cycle_edges.push_back({a,b});
if(cycle_edges.size()==1) new_valid(find_path(a,b));
else if(cycle_edges.size()==2)
{
vector<int> path=find_path(a,b);
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);
for(int x:opt) lim.push_back(limiter(x));
for(limiter &l:lim)
{
for(auto [x,y]:cycle_edges)
{
if(l.inside(x)) l.add_cycle(x,y);
else rm_valid(l.root);
}
}
}
else if(cycle_edges.size()>=3)
{
for(limiter &l:lim)
{
if(l.inside(a)) l.add_cycle(a,b);
else rm_valid(l.root);
}
}
}
upddeg(a);
upddeg(b);
}
int CountCritical()
{
if(four.size()==0) return cnt[bad]+(bad>0?cntbad[bad-1]:0);
else if(four.size()==1) return (valid[four[0]]&&big[four[0]]==bad-1);
else return 0;
}
