#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000001;
vector<int> adj[N];
int U_i[N], V_i[N];
int small_case, cycle, gg, tot;
int deg[N], p[N], sz[N];
int n, ans;
class solve {
private:
int deg[N], p[N];
int fr(int i) {
return p[i] == i ? i : p[i] = fr(p[i]);
}
public:
int root, ans;
void Link(int A, int B) {
if (!ans) return;
if (A == root || B == root) return;
if (++deg[A] == 3 || ++deg[B] == 3) {
ans = 0;
return;
}
int pa = fr(A), pb = fr(B);
if (pa == pb) {
ans = 0;
return;
}
p[pb] = pa;
}
void init() {
ans = 1;
for (int i = 0;i < n;i++) p[i] = i;
for (int i = 0;i < tot;i++) {
Link(U_i[i], V_i[i]);
}
}
} U[4];
int fr(int i) {
return p[i] == i ? i : p[i] = fr(p[i]);
}
void Init(int N_) {
n = N_;
ans = n;
for (int i = 0;i < n;i++) p[i] = i, sz[i] = 1;
}
void Link(int A, int B) {
U_i[tot] = A, V_i[tot] = B, tot++;
if (gg) return;
if (small_case) {
for (int i = 0;i < 4;i++) U[i].Link(A, B);
return;
}
adj[A].push_back(B);
adj[B].push_back(A);
if (++deg[A] == 3) {
small_case = 1;
U[0].root = A;
int idx = 1;
for (auto& x : adj[A]) U[idx++].root = x;
}
if (++deg[B] == 3) {
small_case = 1;
U[0].root = B;
int idx = 1;
for (auto& x : adj[B]) U[idx++].root = x;
}
if (small_case) {
for (int i = 0;i < 4;i++) U[i].init();
return;
}
int pa = fr(A), pb = fr(B);
if (pa == pb) {
if (!cycle) ans = sz[pa], cycle = 1;
else gg = 1;
}
else sz[pa] += sz[pb], p[pb] = pa;
}
int CountCritical() {
if (gg) return 0;
if (!small_case) return ans;
return U[0].ans + U[1].ans + U[2].ans + U[3].ans;
}
