#include <vector>
using namespace std;
int n;
vector<int> edge[1000001];
int phase;
int ans;
void Init(int N) {
n = N;
phase = 0;
ans = n;
}
struct _uf {
int par[1000001];
int sz[1000001];
int st;
int disactive;
_uf() {
for (int i = 1; i <= 1000000; ++i) sz[i] = 1;
}
int find(int x) {
if (par[x]) return par[x] = find(par[x]);
return x;
}
int merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return 0;
if (sz[x] < sz[y]) swap(x, y);
par[y] = x;
sz[x] += sz[y];
return 1;
}
void disMerge(int x, int y) {
if (!merge(x, y)) disactive = 1;
}
void init(int S) {
st = S;
for (int i = 1; i <= n; ++i) {
if (i == S) continue;
for (int j : edge[i]) {
if (j == S) continue;
if (i < j) disMerge(i, j);
}
}
}
void off(const vector<int> &v) {
if (disactive) return;
for (int i : v) if (st == i) return;
disactive = 1;
}
} uf[5];
void changePhase(int x) {
phase = 1;
uf[1].init(x);
int T = 1;
for (int i : edge[x]) uf[++T].init(i);
}
void checkDeg(int x) {
if (edge[x].size() < 3) return;
vector<int> ch;
ch.push_back(x);
if (edge[x].size() == 3) {
for (int i : edge[x]) ch.push_back(i);
}
int d = 0;
for (int i = 1; i <= 4; ++i) {
uf[i].off(ch);
d += uf[i].disactive;
}
if (d == 4) phase = 2;
}
int cyc = 0;
void Link(int A, int B) {
++A; ++B;
edge[A].push_back(B);
edge[B].push_back(A);
int iniPhase = phase;
if (phase == 0) {
if (edge[A].size() > 2) changePhase(A);
else if (edge[B].size() > 2) changePhase(B);
else {
if (!uf[0].merge(A, B)) {
if (cyc++ == 0) ans = uf[0].sz[uf[0].find(A)];
else phase = 2;
}
}
}
if (phase == 1) checkDeg(A);
if (phase == 1) checkDeg(B);
if (phase == 1 && iniPhase == 1) {
for (int i = 1; i <= 4; ++i) {
if (A == uf[i].st || B == uf[i].st) continue;
uf[i].disMerge(A, B);
}
int d = 0;
for (int i = 1; i <= 4; ++i) d += uf[i].disactive;
if (d == 4) phase = 2;
}
}
int CountCritical() {
if (phase == 0) return ans;
if (phase == 1) {
int ret = 0;
for (int i = 1; i <= 4; ++i) {
if (uf[i].disactive) continue;
++ret;
}
return ret;
}
return 0;
}
