#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 1e6 + 5;
struct Dsu {
vi par, sz, deg;
vector<set<pii, greater<pii>>> degs;
set<int> bad_comps;
int erased_node;
bool good = true;
Dsu() {}
Dsu(int n, int node): erased_node(node) {
par.resize(n), sz.resize(n), deg.resize(n);
degs.resize(n);
for (int i = 0; i < n; i++) {
par[i] = i, sz[i] = 1;
degs[i].insert({0, i});
}
}
int Find(int i) {
return par[i] == i ? i : par[i] = Find(par[i]);
}
void Union(int a, int b) {
int pa = Find(a), pb = Find(b);
if (pa == pb) {
bad_comps.insert(pa);
good = false;
return;
}
if (sz[pa] < sz[pb]) swap(pa, pb);
if (bad_comps.count(pb)) {
bad_comps.erase(bad_comps.find(pb));
bad_comps.insert(pa);
good = false;
}
sz[pa] += sz[pb];
par[pb] = pa;
for (pii p : degs[pb]) {
degs[pa].insert(p);
}
degs[pb].clear();
}
void Add(int a, int b) {
if (a == erased_node || b == erased_node) return;
Union(a, b);
int pa = Find(a);
degs[pa].erase(degs[pa].find({deg[a], a}));
degs[pa].erase(degs[pa].find({deg[b], b}));
deg[a]++, deg[b]++;
degs[pa].insert({deg[a], a});
degs[pa].insert({deg[b], b});
if (deg[a] > 2 || deg[b] > 2) {
bad_comps.insert(pa);
good = false;
}
}
};
int n;
Dsu d1;
bool changed = false;
vi graph[MAX_N];
void Init(int N_) {
n = N_;
d1 = Dsu(n, -1);
}
vector<Dsu> dsu;
vii edges;
void Link(int a, int b) {
graph[a].push_back(b);
graph[b].push_back(a);
edges.push_back({a, b});
if (!changed) {
d1.Add(a, b);
} else {
for (auto &d : dsu) {
d.Add(a, b);
}
}
}
int CountCritical() {
if (changed) {
int cnt = 0;
for (auto &d : dsu) cnt += d.good;
return cnt;
}
if (d1.good) return n;
if (d1.bad_comps.size() == 1) {
int node = *d1.bad_comps.begin();
auto [max_deg, v] = *d1.degs[node].begin();
if (max_deg == 2) return d1.sz[node];
changed = true;
int cnt = 0;
dsu.push_back(Dsu(n, v));
if (max_deg <= 3) {
for (int neighbor : graph[v]) {
dsu.push_back(Dsu(n, neighbor));
}
}
for (auto &d : dsu) {
for (pii p : edges) {
d.Add(p.x, p.y);
}
}
return CountCritical();
}
changed = true;
return 0;
}
