#include <bits/stdc++.h>
using namespace std;
struct ComponentUnionFind {
bool is_chains = true;
vector<int> par;
vector<int> _degree;
int extra_edges = 0;
ComponentUnionFind(int n) : par(n, -1), _degree(n, 0) {}
int find(int i) {
return par[i] < 0 ? i : (par[i] = find(par[i]));
}
int csize(int i) {
return -par[find(i)];
}
int degree(int i) {
return _degree[i];
}
bool join(int i, int j) {
++_degree[i]; ++_degree[j];
if (_degree[i] > 2 || _degree[j] > 2) is_chains = false;
int ir = find(i), jr = find(j);
if (ir == jr) {
++extra_edges;
is_chains = false;
return false;
}
if (par[ir] > par[jr]) {
swap(i, j); swap(ir, jr);
}
par[ir] += par[jr]; par[jr] = ir;
return true;
}
};
ComponentUnionFind create_from_ban(const vector<pair<int, int>> &edge_list, int n, int banned) {
ComponentUnionFind cuf(n);
for (auto [u, v] : edge_list) {
if (u != banned && v != banned) cuf.join(u, v);
}
return cuf;
}
struct ParachuteRings {
int n;
vector<pair<ComponentUnionFind, int>> cufs;
vector<pair<int, int>> edge_list;
// size of the first cycle formed
optional<int> critical_cycle_size;
bool spoiled;
ParachuteRings(int n) : n(n), cufs{{ComponentUnionFind(n), -1}}, spoiled(false) {}
ParachuteRings() {}
int count_critical() {
if (spoiled) return 0;
// here, we know the graph is NOT spoiled
else if (cufs.size() > 1) {
int ans = 0;
for (auto &[cuf, _] : cufs) if (cuf.is_chains) ++ans;
return ans;
} else {
// if we have no critical cycle, everything must still be chains
return critical_cycle_size.value_or(n);
}
}
void reset_cufs(int i) {
vector<pair<ComponentUnionFind, int>> new_cufs;
vector<int> bans;
for (auto [u, v] : edge_list) {
if (u == i) bans.push_back(v);
if (v == i) bans.push_back(u);
}
bans.push_back(i);
for (int v : bans) new_cufs.emplace_back(create_from_ban(edge_list, n, v), v);
cufs = new_cufs;
}
void link(int i, int j) {
edge_list.emplace_back(i, j);
if (spoiled) return;
if (cufs.size() > 1) {
for (auto &[cuf, banned] : cufs) {
if (!(i == banned || j == banned)) cuf.join(i, j);
}
} else {
auto &cuf = cufs[0].first;
bool cycle_created = !cuf.join(i, j);
if (cuf.degree(i) > 2 || cuf.degree(j) > 2) {
if (cuf.degree(i) > 2) reset_cufs(i);
else reset_cufs(j);
} else {
// all nodes still have degree <= 2
// now, we must check for cycles
// here, i guarantee cuf is still valid
if (cycle_created) {
if (cuf.extra_edges >= 2) {
// we have two disjoint cycles, spoil the graph now
spoiled = true;
} else {
critical_cycle_size = cuf.csize(i);
}
}
}
// if i fuck up here because i access cuf when i invalidated it that is
// unironically a "muh memory safety!!!!!" moment
}
}
void dump_state() {
return;
cerr << "!!! STATE DUMP " << endl;
if (spoiled) cerr << "spoiled" << endl;
else {
cerr << "crit cycle " << critical_cycle_size.value_or(-1) << endl;
cerr << cufs.size() << "simulations" << endl;
for (auto &[cuf, banned] : cufs) {
cerr << "cuf with ban" << banned << " = " << cuf.is_chains << endl;
}
}
}
};
ParachuteRings pr;
void Init(int N) {
pr = ParachuteRings(N);
pr.dump_state();
}
void Link(int A, int B) {
pr.link(A, B);
pr.dump_state();
}
int CountCritical() {
return pr.count_critical();
pr.dump_state();
}
