#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)v.size()
const int MAXN = 1e6+5;
vector<int> cand, ea, eb, adj[MAXN];
int pai[10][MAXN], tam[10][MAXN], grau[10][MAXN], dr[10], n;
void Init(int N_) {
n = N_;
cand.clear(); ea.clear(); eb.clear();
for(int i = 0; i < n; i++)adj[i].clear();
for(int i = 0; i < n; i++)cand.push_back(i);
for(int x = 0; x < 5; x++){
for(int i = 0; i < n; i++){
pai[x][i] = i;
tam[x][i] = 1;
grau[x][i] = 0;
}
dr[x] = 0;
}
}
int find(int id, int x){
if(pai[id][x] == x)return x;
return pai[id][x] = find(id, pai[id][x]);
}
void merge(int id, int a, int b){
a = find(id,a), b = find(id,b);
if(tam[id][a] < tam[id][b])swap(a,b);
pai[id][b] = a;
tam[id][a] += tam[id][b];
}
void reconstuir(int id, int x){
for(int i = 0; i < n; i++){
pai[id][i] = i;
tam[id][i] = 1;
grau[id][i] = 0;
}
dr[id] = 0;
for(int i = 0; i < sz(ea); i++){
int a = ea[i], b = eb[i];
if(a == x || b == x)continue;
if(find(id,a) == find(id,b)){dr[id] = 1; return;}
if(grau[id][a] > 1 || grau[id][b] > 1){dr[id] = 1; return;}
merge(id,a,b);
grau[id][a]++; grau[id][b]++;
}
}
void checarGrau(int a){
if(grau[0][a] == 4 && sz(cand) > 1){
cand.clear();
cand.push_back(a);
reconstuir(1,a);
}else if(grau[0][a] == 3 && sz(cand) > 4){
cand.clear();
cand.push_back(a);
for(int viz : adj[a])cand.push_back(viz);
for(int i = 0; i < sz(cand); i++)
reconstuir(i+1,cand[i]);
}
}
void Link(int a, int b) {
grau[0][a]++; grau[0][b]++;
adj[a].push_back(b); adj[b].push_back(a);
checarGrau(a);
checarGrau(b);
ea.push_back(a); eb.push_back(b);
if(find(0,a) == find(0,b)){
if(dr[0] == 0)dr[0] = a;
else dr[0] = -1;
}
merge(0,a,b);
for(int i = 0; i < sz(cand); i++){
if(dr[i+1] || a == cand[i] || b == cand[i])continue;
if(find(i+1,a) == find(i+1,b)){dr[i+1] = 1; continue;}
if(grau[i+1][a] > 1 || grau[i+1][b] > 1){dr[i+1] = 1; continue;}
merge(i+1,a,b);
grau[i+1][a]++; grau[i+1][b]++;
}
}
int CountCritical() {
if(sz(cand) == n){
if(dr[0] == -1)return 0;
if(dr[0] == 0)return n;
return tam[0][find(0,dr[0])];
}else{
int ans = 0;
for(int i = 0; i < sz(cand); i++)
if(!dr[i+1])ans++;
return ans;
}
}
