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