#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 20;
vector<pair<int, int>> edges;
int deg[4][maxn];
int L[4][maxn];
int R[4][maxn];
int len[maxn];
int cand[4];
bool good[4];
int n;
int cycle;
void Init(int _n) {
n = _n;
for (int k = 0; k < 4; k++) {
cand[k] = -1;
}
for (int i = 0; i < n; i++) {
L[0][i] = i;
R[0][i] = i;
len[i] = 1;
}
}
void update(int k, int u, int v) {
if (!good[k]) {
return;
}
if (u == cand[k] || v == cand[k]) {
return;
}
if (deg[k][u] == 2 || deg[k][v] == 2) {
good[k] = false;
return;
}
deg[k][u]++;
deg[k][v]++;
int lu = L[k][u];
int ru = R[k][u];
int lv = L[k][v];
int rv = R[k][v];
if (lu == lv) {
good[k] = false;
return;
}
if (lu == u) {
swap(lu, ru);
L[k][lu] = lu;
L[k][ru] = lu;
R[k][lu] = ru;
R[k][ru] = ru;
}
if (rv == v) {
swap(lv, rv);
L[k][lv] = lv;
L[k][rv] = lv;
R[k][lv] = rv;
R[k][rv] = rv;
}
L[k][lu] = lu;
R[k][lu] = rv;
L[k][rv] = lu;
R[k][rv] = rv;
}
void Link(int u, int v) {
if (cand[0] == -1) {
edges.emplace_back(u, v);
deg[0][u]++;
deg[0][v]++;
if (deg[0][v] == 3) {
swap(u, v);
}
if (deg[0][u] == 3) {
cand[0] = u;
int cnt = 0;
for (auto e: edges) {
if (e.first == u) {
cand[++cnt] = e.second;
}
else if (e.second == u) {
cand[++cnt] = e.first;
}
}
for (int k = 0; k < 4; k++) {
good[k] = true;
for (int i = 0; i < n; i++) {
deg[k][i] = 0;
L[k][i] = i;
R[k][i] = i;
}
}
for (auto e: edges) {
for (int k = 0; k < 4; k++) {
update(k, e.first, e.second);
}
}
edges.clear();
}
else {
int len_u = len[u];
int len_v = len[v];
int lu = L[0][u];
int ru = R[0][u];
int lv = L[0][v];
int rv = R[0][v];
if (lu == lv) {
if (cycle == 0) {
cycle = len_u;
}
else {
cycle = -1;
}
return;
}
if (lu == u) {
swap(lu, ru);
L[0][lu] = lu;
L[0][ru] = lu;
R[0][lu] = ru;
R[0][ru] = ru;
}
if (rv == v) {
swap(lv, rv);
L[0][lv] = lv;
L[0][rv] = lv;
R[0][lv] = rv;
R[0][rv] = rv;
}
L[0][lu] = lu;
R[0][lu] = rv;
L[0][rv] = lu;
R[0][rv] = rv;
len[lu] = len_u + len_v;
len[rv] = len_u + len_v;
}
}
else {
for (int k = 0; k < 4; k++) {
update(k, u, v);
}
}
}
int CountCritical() {
if (cand[0] == -1) {
if (cycle == 0) {
return n;
}
else if (cycle == -1) {
return 0;
}
else {
return cycle;
}
}
else {
return good[0] + good[1] + good[2] + good[3];
}
}
