#include <bits/stdc++.h>
using namespace std;
#define synchronize {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
const int nmax = 1e6 + 5;
int theta, n, q;
int u, v, cyc, res;
bool check = false;
int par[nmax], sz[nmax], deg[nmax];
vector<pii> edges;
vector<int> adj[nmax];
struct DSU {
int root, ans;
vector<int> par, deg;
DSU() {
ans = 1;
root = 0;
par.resize(nmax + 1);
deg.resize(nmax + 1);
for (int i = 1; i <= nmax; i++) {
par[i] = i;
deg[i] = 0;
}
}
void init() {
ans = 1;
for (int i = 1; i <= n; i++) {
par[i] = i;
// deg[i] = 0;
}
for (auto [u, v] : edges) {
merge(u, v);
}
}
int find(int u) {
if (u == par[u]) return u;
return par[u] = find(par[u]);
}
void merge(int u, int v) {
if (u == root || v == root || ans == 0) return;
if (++deg[u] == 3) ans = 0;
if (++deg[v] == 3) ans = 0;
u = find(u), v = find(v);
if (u == v) {
ans = 0;
return;
}
par[u] = v;
}
} ds[4];
int find(int u) {
if (u == par[u]) return u;
return par[u] = find(par[u]);
}
void Init(int _n) {
n = _n;
for (int i = 1; i <= n; i++) {
par[i] = i;
deg[i] = 0;
sz[i] = 1;
}
}
void Link(int u, int v) {
if (check) {
for (int i = 0; i < 4; i++)
ds[i].merge(u, v);
return;
}
edges.push_back({u, v});
adj[u].push_back(v);
adj[v].push_back(u);
if (deg[u] == 2 || deg[v] == 2) check = true;
if (++deg[u] == 3) {
ds[0].root = u;
for (int i = 1; i < 4; i++) ds[i].root = adj[u][i - 1];
for (int i = 0; i < 4; i++) ds[i].init();
return;
}
if (++deg[v] == 3) {
ds[0].root = v;
for (int i = 1; i < 4; i++) ds[i].root = adj[v][i - 1];
for (int i = 0; i < 4; i++) ds[i].init();
return;
}
u = find(u), v = find(v);
if (u == v) {
res = sz[u];
cyc++;
} else {
sz[u] += sz[v];
par[v] = u;
}
}
int CountCritical() {
if (cyc > 1) return 0;
if (check) return ds[0].ans + ds[1].ans + ds[2].ans + ds[3].ans;
if (cyc == 1) return res;
return n;
}
