#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int pai[MAXN][5], sz[MAXN][5];
int id[MAXN];
int deg[MAXN][5];
set<int> comp_ciclos;
vector<int> cand_critical;
vector<int> adj[MAXN];
vector<pair<int, int>> links;
bool first_update;
vector<int> deg_3, deg_4;
int get(int v, int x){
if(v == pai[v][x]) return v;
return pai[v][x] = get(pai[v][x], x);
}
void dsu_union(int a, int b, int x){
a = get(a, x);
b = get(b, x);
if(sz[a][x] > sz[b][x]) swap(a, b);
pai[a][x] = b;
sz[b][x] += sz[a][x];
}
int n;
void Init(int n_){
n = n_;
comp_ciclos.clear();
cand_critical.clear();
deg_3.clear();
deg_4.clear();
first_update = true;
for(int i=1; i<=n; i++) id[i] = -1;
for(int i=1; i<=n; i++){
for(int j=0; j<5; j++){
sz[i][j] = 1;
pai[i][j] = i;
deg[i][j] = 0;
}
}
}
void dsu_init(int v){
for(auto [a, b] : links){
if(a == v || b == v) continue;
if(get(a, id[v]) == get(b, id[v])){
id[v] = -1;
} else{
dsu_union(a, b, id[v]);
if(deg[a][id[v]] > 1 || deg[b][id[v]] > 1) id[v] = -1;
}
deg[a][id[v]] ++;
deg[b][id[v]] ++;
}
}
void Link(int a, int b){
a ++;
b ++;
links.push_back({a, b});
adj[a].push_back(b);
adj[b].push_back(a);
for(auto v : cand_critical){
if(id[v] == -1) continue;
if(a == v || b == v) continue;
if(get(a, id[v]) == get(b, id[v])){
id[v] = -1;
} else{
dsu_union(a, b, id[v]);
if(deg[a][id[v]] > 1 || deg[b][id[v]] > 1) id[v] = -1;
}
deg[a][id[v]] ++;
deg[b][id[v]] ++;
}
if(get(a, 0) == get(b, 0)){
comp_ciclos.insert(get(a, 0));
} else dsu_union(a, b, 0);
deg[a][0] ++;
deg[b][0] ++;
if(deg[a][0] >= 3){
deg_3.push_back(a);
if(deg[a][0] >= 4) deg_4.push_back(a);
}
if(deg[b][0] >= 3){
deg_3.push_back(b);
if(deg[b][0] >= 4) deg_4.push_back(b);
}
vector<int> new_cand_critical;
bool update_cand_critical = false;
if(deg_4.size() > 1){
update_cand_critical = true;
new_cand_critical = {};
} else if(deg_4.size() == 1){
update_cand_critical = true;
int v = deg_4[0];
new_cand_critical = {v};
} else if(deg_3.size() > 0){
update_cand_critical = true;
int v = deg_3[0];
new_cand_critical = {v, adj[v][0], adj[v][1], adj[v][2]};
}
if(update_cand_critical){
if(first_update){
for(auto v : new_cand_critical){
cand_critical.push_back(v);
id[v] = cand_critical.size();
dsu_init(v);
}
first_update = false;
} else{
for(auto v : cand_critical){
bool ok = false;
for(auto u : new_cand_critical) ok |= (u == v);
if(!ok) id[v] = -1;
}
}
}
}
int CountCritical(){
if(deg_3.empty()){
if(comp_ciclos.size() > 1) return 0;
if(comp_ciclos.size() == 1) return sz[get(*comp_ciclos.begin(), 0)][0];
return n;
}
int ans = 0;
for(auto v : cand_critical) if(id[v] != -1) ans ++;
return ans;
}
