#include<bits/stdc++.h>
using namespace std;
int N;
int current_state, ans; // 0: all chain, 1: ring, 2: 1 non-ring 3: return 0
const int maxn = 1e6+5;
int up[maxn], L[maxn], R[maxn];
vector<pair<int, int>> E;
vector<int> g[maxn];
int Find(int x){
return up[x] < 0 ? x : up[x] = Find(up[x]);
}
struct dsu{
int nd, state;
vector<int> up, L, R;
int Find(int x){
return up[x] < 0 ? x : up[x] = Find(up[x]);
}
void Union(int a, int b){
// cout << "UNION " << a << " " << b << endl;
if(a == nd || b == nd)return;
if(!state)return;
int ra = Find(a), rb = Find(b);
if(ra == rb){
state = 0;
return;
}
if(a != L[ra])swap(L[ra], R[ra]);
if(b != L[rb])swap(L[rb], R[rb]);
if(a != L[ra] || b != L[rb]){
state = 0;
return;
}
up[rb] = ra;
L[ra] = R[rb];
}
dsu(int _nd): nd(_nd){
up.assign(N, -1);
L.resize(N);
R.resize(N);
for(int i = 0; i < N; i++)L[i] = R[i] = i;
state = 1;
for(auto v: E)Union(v.first, v.second);
}
};
vector<dsu> candidates;
void init_cen(int x){
current_state = 2;
candidates.push_back(dsu(x));
for(auto v: g[x])candidates.push_back(dsu(v));
}
void Union(int a, int b){ // only happens while in state 0 or 1
int ra = Find(a), rb = Find(b);
if(ra == rb){
if(current_state == 1){
current_state = 3;
return;
}
L[ra] = R[ra] = -1;
current_state = 1;
ans = -up[ra];
}
else {
if(a != L[ra])swap(L[ra], R[ra]);
if(b != L[rb])swap(L[rb], R[rb]);
up[ra] += up[rb];
up[rb] = ra;
L[ra] = R[rb];
}
}
void Init(int N_) {
current_state = 0;
N = N_;
ans = N;
candidates.clear();
E.clear();
for(int i = 0; i < N; i++){
g[i].clear();
up[i] = -1;
L[i] = R[i] = i;
}
}
void Link(int A, int B) {
E.push_back({A, B});
g[A].push_back(B);
g[B].push_back(A);
if(current_state <= 1){
if(g[A].size() >= 3)init_cen(A);
else if(g[B].size() >= 3)init_cen(B);
else Union(A, B);
}
else {
for(auto &v: candidates)v.Union(A, B);
}
}
int CountCritical() {
if(current_state <= 1)return ans;
else {
int sum = 0;
for(auto &v: candidates)sum += v.state;
return sum;
}
}
