#include<bits/stdc++.h>
using namespace std;
struct DSU{
vector<int> sz, anc, oc, deg;
int nbG= 0, nbC= 0, csz = 0, above3 = 0;
DSU(){};
DSU(int l){
sz.resize(l);
anc.resize(l);
oc.resize(l);
deg.resize(l);
nbG = l;
for(int i = 0; i<l; i++){
anc[i] = i;
sz[i] = 1;
deg[i] = 0;
}
oc[0]= l;
}
int c(int u){
if(anc[u] == u){
return u;
}
int v= c(anc[u]);
anc[u] = v;
return v;
}
void changeDeg(int u, int d){
oc[deg[u]]--;
if(deg[u]>=3){
above3--;
}
deg[u]+=d;
if(deg[u]>=3){
above3++;
}
oc[deg[u]]++;
}
void merge(int a, int b){
changeDeg(a, +1);
changeDeg(b, +1);
a= c(a);
b = c(b);
if(a==b){
nbC++;
csz = sz[a];
return;
}
nbG--;
if(sz[a]<sz[b]){
swap(a, b);
}
anc[b]= a;
sz[a]+=sz[b];
}
};
struct multiDSU{
unordered_map<int, DSU> dsus;
multiDSU(){};
multiDSU(int l, unordered_set<int>& intresting){
for(auto e: intresting){
dsus[e] = DSU(l);
}
dsus[-1] = DSU(l);
}
void merge(int a, int b){
for(auto it = dsus.begin(); it!=dsus.end(); ++it){
if(it->first != a && it->first != b){
//cerr<<"merging "<<a<<" "<<b<<" "<<it->first<<endl;
it->second.merge(a, b);
}
}
}
};
const int MAX_N = 1e6;
vector<int> adj[MAX_N];
DSU beginDSU;
multiDSU endDSU;
int N;
int state = 0;
//0 = only 2s
//1 = have a 3 or more
void Init(int _N){
N = _N;
beginDSU = DSU(N);
}
void Link(int a, int b){
if(state == 0){
beginDSU.merge(a, b);
adj[a].push_back(b);
adj[b].push_back(a);
if(adj[a].size()<3){
swap(a, b);
}
if(adj[a].size() >= 3){
state = 1;
unordered_set<int> intresting;
for(auto o: adj[a]){
intresting.insert(o);
}
intresting.insert(a);
endDSU = multiDSU(N, intresting);
for(int i = 0; i<N; i++){
for(auto e: adj[i]){
if(i<e){
endDSU.merge(e, i);
}
}
}
}
}
else{
endDSU.merge(a, b);
}
}
int CountCritical(){
if(state== 0){
if(beginDSU.nbC == 0){
return N;
}
else if(beginDSU.nbC == 1){
return beginDSU.csz;
}
else{
return 0;
}
}
else{
int res= 0;
for(auto e: endDSU.dsus){
if(e.first != -1){
if((e.second.oc[0]-1)*2 + e.second.oc[1] == 2*(e.second.nbG-1) && e.second.above3 == 0){
res++;
}
else{
}
}
}
return res;
}
}
