#include <numeric>
#include <vector>
struct DSU {
std::vector<int> p, r;
explicit DSU(int n) : p(n), r(n, 1) { iota(p.begin(), p.end(), 0); }
int find(int i) { return i == p[i] ? i : p[i] = find(p[i]); }
bool merge(int i, int j) {
i = find(i);
j = find(j);
if (i == j) return false;
if (r[i] > r[j]) std::swap(i, j);
p[i] = j;
r[j] += r[i];
return true;
}
};
struct World {
std::vector<int> c;
DSU dsu;
int killed;
explicit World(int n) : c(n), dsu(n), killed(-1) {}
};
static int n;
static std::vector<World> worlds;
static std::vector<std::vector<int>> g;
static bool many;
static int cyc;
void Init(int n) {
::n = n;
worlds.emplace_back(n);
g.assign(n, {});
many = false;
cyc = -1;
}
void Link(int a, int b) {
if (many) {
for (int i = worlds.size(); i--;) {
auto &[c, dsu, k] = worlds[i];
if (a == k || b == k) continue;
c[a] += 1;
c[b] += 1;
if (c[a] > 2 || c[b] > 2 || !dsu.merge(a, b)) {
worlds[i] = std::move(worlds.back());
worlds.pop_back();
}
}
} else {
auto &[c, dsu, _] = worlds[0];
g[a].push_back(b);
g[b].push_back(a);
c[a] += 1;
c[b] += 1;
if (c[a] > 2 || c[b] > 2) {
auto x = c[a] > 2 ? a : b;
std::vector<int> ks = g[x];
ks.push_back(x);
worlds.clear();
many = true;
for (auto k : ks) {
worlds.emplace_back(n);
worlds.back().killed = k;
}
for (int i = 0; i < n; ++i)
for (auto j : g[i])
if (i < j) Link(i, j);
return;
}
if (!dsu.merge(a, b)) {
if (cyc == -1) {
cyc = a;
} else {
worlds.clear();
many = true;
}
return;
}
}
}
int CountCritical() {
if (many) {
return worlds.size();
} else {
auto &[_, dsu, __] = worlds[0];
return cyc != -1 ? dsu.r[dsu.find(cyc)] : n;
}
}
