#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, deg[nmax + 7], st, en, par[nmax + 7];
bool ok[nmax + 7], vis[nmax + 7], four, found_cycle = 0;
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);
dsu.init(n);
}
void dfs(int i, int j) {
vis[i] = 1;
for (auto x: adj[i]) {
if (x == j) {
continue;
}
if (vis[x]) {
en = x;
st = i;
continue;
}
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 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();
for (auto x: ans) {
ok[x] = 1;
}
vector < int > ().swap(ans);
for (auto x: cycle) {
if (ok[x]) {
ans.push_back(x);
}
}
REP(i, n) {
ok[i] = 0;
}
}
}
for (auto x: {A, B}) {
if (sz(adj[x]) == 4) {
if (four) {
vector < int > ().swap(ans);
return;
}
else {
bool ok = 0;
for (auto i: ans) {
if (i == x) {
ok = 1;
}
}
if (ok) {
ans.push_back(x);
}
}
}
if (sz(adj[x]) == 3) {
for (auto i: adj[x]) {
ok[i] = 1;
}
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 i: adj[x]) {
ok[i] = 0;
}
ok[x] = 0;
}
}
}
int CountCritical() {
return sz(ans);
}
