#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())
const int nmax = 1e6;
int n, st = 0, en = 0, par[nmax + 7];
bool ok[nmax + 7], vis[nmax + 7], four, found_cycle = 0, fc;
vector < int > ans, adj[nmax + 7];
struct DSU {
int sz[nmax + 7], par[nmax + 7];
void init(int n) {
iota(par, par + n, 0);
REP(i, n) {
sz[i] = 1;
}
}
int find_par(int i) {
return (par[i] == i ? i : par[i] = find_par(par[i]));
}
bool unite(int u, int v) {
u = find_par(u);
v = find_par(v);
if (u == v) {
return 0;
}
if (sz[u] < sz[v]) {
swap(u, v);
}
par[v] = u;
sz[u] += sz[v];
return 1;
}
}dsu;
void Init(int N_) {
n = N_;
ans.resize(n);
iota(ans.begin(), ans.end(), 0);
REP(i, n) {
adj[i].push_back(i);
}
dsu.init(n);
}
void dfs(int i, int j) {
// cout << "dfs " << j << " " << i << "\n";
vis[i] = 1;
for (auto x: adj[i]) {
if (en || st) {
break;
}
// cout << "edge " << i << " " << x << "\n";
if (x == j || x == i) {
continue;
}
if (vis[x]) {
en = i;
st = x;
break;
}
par[x] = i;
dfs(x, i);
}
}
vector < int > find_cycle() {
REP(i, n) {
if (!vis[i]) {
dfs(i, -1);
}
}
// REP(i, n) {
// cout << vis[i] << " " << par[i] << "\n";
// }
// cout << st << " " << en << "\n";
vector < int > cycle;
while (en != st) {
// cerr << en << "\n";
cycle.push_back(en);
en = par[en];
}
cycle.push_back(en);
return move(cycle);
}
void add(vector < int > &vec) {
// cout << "add ";
// for (auto x: vec) {
// cout << x << " ";
// }
// cout << "\n";
for (auto x: vec) {
ok[x] = 1;
}
for (auto &x: ans) {
if (!ok[x]) {
x = -1;
}
}
sort(ans.begin(), ans.end(), greater < int > ());
while (!ans.empty() && ans.back() == -1) {
ans.pop_back();
}
for (auto x: vec) {
ok[x] = 0;
}
}
void Link(int A, int B) {
if (ans.empty()) {
return;
}
adj[A].push_back(B);
adj[B].push_back(A);
if (!dsu.unite(A, B)) {
if (!found_cycle) {
found_cycle = 1;
vector < int > cycle = find_cycle();
add(cycle);
}
else {
if (dsu.find_par(ans[0]) != dsu.find_par(A)) {
vector < int > ().swap(ans);
return;
}
fc = 1;
for (auto &x: ans) {
if (sz(adj[x]) < 4) {
x = -1;
}
}
sort(ans.begin(), ans.end(), greater < int > ());
while (!ans.empty() && ans.back() == -1) {
ans.pop_back();
}
}
}
for (auto x: {A, B}) {
if (sz(adj[x]) == 5) {
if (four) {
vector < int > ().swap(ans);
return;
}
else {
four = 1;
bool ok = 0;
for (auto i: ans) {
if (i == x) {
ok = 1;
}
}
vector < int > ().swap(ans);
if (ok) {
ans.push_back(x);
}
}
}
if (sz(adj[x]) == 4) {
add(adj[x]);
}
}
// cout << "link " << A << " " << B << "\n";
// for (auto x: ans) {
// cout << x << " ";
// }
// cout << "\n";
}
int CountCritical() {
// for (auto x: ans) {
// cout << x << " ";
// }
// cout << "\n";
return sz(ans);
}
