#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
struct dsu {
vector<int> p;
vector<int> sz;
int n;
dsu(int _n) : n(_n) {
p = vector<int>(n);
iota(p.begin(), p.end(), 0);
sz = vector<int>(n, 1);
}
inline int get(int x) {
if (p[x] == x) {
return x;
} else {
return p[x] = get(p[x]);
}
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) {
return false;
}
p[x] = y;
sz[y] += sz[x];
return true;
}
inline bool same(int x, int y) {
return (get(x) == get(y));
}
inline int size(int x) {
return sz[get(x)];
}
inline bool root(int x) {
return (x == get(x));
}
};
int n;
int mx;
vector<vector<int>> g;
vector<int> deg;
dsu uf = 1;
struct info {
int ignore;
int ok;
vector<int> ideg;
dsu iuf = 1;
info(int ignore_) {
ignore = ignore_;
ok = 1;
ideg = vector<int>(n);
iuf = dsu(n);
for (int i = 0; i < n; i++) {
for (int j : g[i]) {
if (i == ignore || j == ignore || i > j) {
continue;
}
if (!iuf.unite(i, j)) {
ok = 0;
}
ideg[i]++;
ideg[j]++;
}
}
if (*max_element(ideg.begin(), ideg.end()) > 2) {
ok = 0;
}
}
void add(int x, int y) {
if (x == ignore || y == ignore || ok == 0) {
return;
}
ideg[x]++;
ideg[y]++;
if (max(ideg[x], ideg[y]) > 2) {
ok = 0;
return;
}
if (!iuf.unite(x, y)) {
ok = 0;
return;
}
}
};
vector<info> cands;
vector<int> loops;
void Init(int n_) {
n = n_;
g = vector<vector<int>>(n);
deg = vector<int>(n);
uf = dsu(n);
}
void Link(int x, int y) {
g[x].emplace_back(y);
g[y].emplace_back(x);
deg[x]++;
deg[y]++;
bool t = uf.unite(x, y);
int new_mx = max({mx, deg[x], deg[y]});
if (new_mx == 3 && mx == 2) {
if (deg[x] == 3) {
cands.emplace_back(info(x));
} else {
cands.emplace_back(info(y));
}
for (int z : g[cands[0].ignore]) {
cands.emplace_back(info(z));
}
} else if (mx <= 2) {
if (!t) {
loops.emplace_back(uf.get(x));
}
} else {
for (int i = 0; i < 4; i++) {
cands[i].add(x, y);
}
}
swap(mx, new_mx);
}
int CountCritical() {
int ans = 0;
if (mx >= 3) {
for (int i = 0; i < 4; i++) {
ans += cands[i].ok;
}
} else {
if (loops.size() == 0) {
ans = n;
} else if (loops.size() == 1) {
ans = uf.size(loops[0]);
}
}
return ans;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Init(7);
cout << CountCritical() << endl; // 7
Link(1, 2);
cout << CountCritical() << endl; // 7
Link(0, 5);
cout << CountCritical() << endl; // 7
Link(2, 0);
cout << CountCritical() << endl; // 7
Link(3, 2);
cout << CountCritical() << endl; // 4
Link(3, 5);
cout << CountCritical() << endl; // 3
Link(4, 3);
cout << CountCritical() << endl; // 2
return 0;
}
#endif
