#include <bits/stdc++.h>
using namespace std;
//#include "rings.h"
vector<vector<int>> G; set<int> D,C,F;
int n;
bool f;
multiset<pair<int,int>> Y;
vector<int> UF,SZ;
stack<pair<int,int>> S;
int root(int x){
if (UF[x]==-1) return x;
return root(UF[x]);
}
void Init(int N){
n = N;
G.assign(n,vector<int>()),D.clear(),C.clear(),Y.clear(),F.clear(),f = false;
UF.assign(n,-1),SZ.assign(n,1);
}
bool merge(int a,int b,bool c = false){
if (c&&root(a)==root(b)) return false;
a = root(a),b = root(b);
if (SZ[a]>SZ[b]) swap(a,b);
UF[a] = b,SZ[b] += SZ[a];
if (c) S.emplace(a,b);
if (C.contains(a)) C.erase(a),C.emplace(b);
return c;
}
void rollback(){
while(!S.empty()){
auto [a,b] = S.top(); S.pop();
UF[a] = -1,SZ[b] -= SZ[a];
}
}
void rebuildF(){
if (F.size()>1){
f = true;
return;
}
Y.clear(),C.clear(),fill(UF.begin(),UF.end(),-1),fill(SZ.begin(),SZ.end(),1);
D.clear();
int x = *F.begin();
G[x].clear();
for (int i(0);i < n;++i){
auto it = find(G[i].begin(),G[i].end(),x);
if (it!=G[i].end()) G[i].erase(it);
if (G[i].size()>=3) f = true;
}
for (int i(0);i < n;++i) for (int k:G[i]) if (i<k){
if (root(i)==root(k)) C.emplace(root(i));
else merge(i,k);
}
}
void rebuild(){
if (!F.empty()) return rebuildF();
if (D.size()>3) f = true;
if (f) return;
Y.clear(),C.clear(),fill(UF.begin(),UF.end(),-1),fill(SZ.begin(),SZ.end(),1);
vector<int> T;
for (int i:D){
T.emplace_back(i);
for (int k:G[i]) T.emplace_back(k);
}
sort(T.begin(),T.end());
for (int i(0);i < n;++i) for (int k:G[i]) if (i<k){
if (binary_search(T.begin(),T.end(),i)&&binary_search(T.begin(),T.end(),k)){
Y.emplace(i,k);
} else {
if (root(i)==root(k)) C.emplace(root(i));
else merge(i,k);
}
}
}
void Link(int a,int b){
if (!F.empty()&&(*F.begin()==a||*F.begin()==b)) return;
if ((G[a].size()==2||G[b].size()==2)&&!F.empty()) f = true;
if (f) return;
G[a].emplace_back(b);
if (G[a].size()==3) D.emplace(a);
if (G[a].size()>3) F.emplace(a),rebuildF();
if (!F.empty()&&*F.begin()==a) return;
G[b].emplace_back(a);
if (G[b].size()==3) D.emplace(b);
if (G[b].size()>3) F.emplace(b),rebuildF();
if (!F.empty()&&(*F.begin()==a||*F.begin()==b)) return;
if (F.empty()&&(G[a].size()>=3||G[b].size()>=3)) rebuild();
else if (root(a)==root(b)) C.emplace(root(a));
else merge(a,b);
}
int CountCritical(){
if (f) return 0;
if (!F.empty()){
if (C.empty()&&D.empty()) return 1;
return 0;
}
if (!D.empty()&&!C.empty()) return 0;
if (C.size()>1) return 0;
if (C.size()==1) return SZ[root(*C.begin())];
if (C.empty()&&D.empty()) return n;
int ret = 0;
vector<int> T;
for (int i:D){
T.emplace_back(i);
for (int k:G[i]) T.emplace_back(k);
}
sort(T.begin(),T.end()),T.erase(unique(T.begin(),T.end()),T.end());
for (int i:T){
int res = 1;
for (int k:D) if (i!=k&&find(G[k].begin(),G[k].end(),i)==G[k].end()) res = 0;
if (res==0) continue;
for (auto [a,b]:Y) if (a!=i&&b!=i) res &= merge(a,b,true);
ret += res,rollback();
}
return ret;
}
