#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;
const int Nn = 1e6 + 6;
bool cycle, us[Nn];
int n, p[Nn], sz[Nn], pr[Nn], cr[Nn];
vector < int > v[Nn];
set < int > ans;
int P(int x) {
if (p[x] == x) return x;
return p[x] = P(p[x]);
}
void Init(int N_) {
n = N_;
for (int i = 0; i < n; ++i) {
ans.insert(i);
p[i] = i;
}
}
void intr(set < int > cur) {
int crs = 0;
for (set < int > :: iterator it = cur.begin(); it != cur.end(); ++it) {
if (ans.find(*it) == ans.end()) continue;
cr[++crs] = (*it);
}
ans.clear();
for (int i = 1; i <= crs; ++i) {
ans.insert(cr[i]);
}
}
vector < int > rec;
void dfs(int x, int p, int fn) {
pr[x] = p;
us[x] = true;
rec.pb(x);
if (x == fn) {
set < int > cur;
cur.insert(x);
x = pr[x];
cycle = true;
while (x != fn) {
cur.insert(x);
x = pr[x];
}
intr(cur);
return ;
}
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i];
if (to != p && !us[to]) dfs(to, x, fn);
if (cycle) return ;
}
}
void Link(int A, int B) {
int ap = P(A), bp = P(B);
v[A].pb(B), v[B].pb(A);
if (ap != bp) {
if (sz[ap] < sz[bp]) swap(ap, bp);
sz[ap] += sz[bp];
p[bp] = ap;
}
else {
++sz[ap];
if (sz[ap] <= 3) {
cycle = false;
dfs(A, B, B);
}
for (int i = 0; i < rec.size(); ++i) {
us[rec[i]] = false;
}
rec.clear();
if (sz[ap] == 2) {
set < int > cur;
int crs = 0;
for (set < int > :: iterator it = ans.begin(); it != ans.end(); ++it) {
if (v[(*it)].size() >= 3) {
cr[++crs] = (*it);
}
}
ans.clear();
for (int i = 1; i <= crs; ++i) {
ans.insert(cr[i]);
}
}
}
set < int > st;
if (v[A].size() == 4) st.clear(), st.insert(A), intr(st);
if (v[B].size() == 4) st.clear(), st.insert(B), intr(st);
if (v[A].size() == 3) st.clear(), st.insert(A), st.insert(v[A][0]), st.insert(v[A][1]), st.insert(v[A][2]), intr(st);
if (v[B].size() == 3) st.clear(), st.insert(B), st.insert(v[B][0]), st.insert(v[B][1]), st.insert(v[B][2]), intr(st);
}
int CountCritical() {
return ans.size();
}
