# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int MX = 1e6 + 5;
int n, a, b, p[MX], bad_deg[MX],par[4][MX],sz[MX],cnt_cyc = 0,cyc_len = 0, cycles[MX];
int deg_[4][MX], in_deg[MX],can[MX];
vector <int> v[MX], pot;
void Init(int N_) {
n = N_;
for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
}
int get_col(int a) {
if (a == p[a]) return a;
else return p[a] = get_col(p[a]);
}
void col(int a, int b) {
a = get_col(a);
b = get_col(b);
if (a == b) {
cnt_cyc++;
cyc_len = sz[a];
return ;
}
if (sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
p[b] = a;
sz[b] = 0;
}
int get_col(int a, int ty) {
if (a == par[ty][a]) return a;
else return par[ty][a] = get_col(par[ty][a], ty);
}
void join(int a, int b, int ty) {
// cout<<"join "<<a<<" "<<get_col(a, ty)<<" "<<b<<" "<<get_col(b, ty)<<" "<<ty<<"\n";
deg_[ty][a]++; deg_[ty][b]++;
a = get_col(a, ty);
b = get_col(b, ty);
if (a == b) {
// cout<<"tyy "<<ty<<"\n";
cycles[ty]++;
return ;
}
if(deg_[ty][a] > 2 || deg_[ty][b] > 2) bad_deg[ty] = 1;
par[ty][b] = a;
}
void build(int a, int ty) {
//cout<<"build "<<ty<<" "<<a<<"\n";
for (int i = 1; i <= n; i++) {
par[ty][i] = i;
}
for (int i = 1; i <= n; i++) {
for (int x : v[i]) {
if (i != a && x != a && i < x) join(i, x, ty);
}
}
}
map <int, bool> adj[MX];
void Link(int A, int B) {
A++; B++;
a = A; b = B;
in_deg[a]++; in_deg[b]++;
adj[a][b] = 1; adj[b][a] = 1;
v[a].pb(b); v[b].pb(a);
int ff = 0;
if (in_deg[a] == 4) {
assert(pot.size());
int is_a = 0;
for (int x : pot) if (x == a) is_a = 1;
if (is_a == 0) {
pot.clear(); pot.pb(-1);
return ;
} else {
for (int x : pot) can[x] = 0; can[a] = 1;
}
}
if (in_deg[b] == 4) {
assert(pot.size());
int is_b = 0;
for (int x : pot) if (x == b) is_b = 1;
if (is_b == 0) {
pot.clear(); pot.pb(-1);
return ;
} else {
for (int x : pot) can[x] = 0; can[b] = 1;
}
}
if (in_deg[a] == 3 && !pot.size()) {
pot.pb(a); can[a] = 1; ff = 1;
for (int x : v[a]) pot.pb(x),can[x] = 1;
for (int i = 0; i < pot.size(); i++) build(pot[i], i);
} else if (in_deg[a] == 3 && pot.size()) {
for (int x : pot) {
if (x != a && adj[a][x] != 1) can[x] = 0;
}
}
if (in_deg[b] == 3 && !pot.size()) {
pot.pb(b); can[b] = 1; ff = 1;
for (int x : v[b]) pot.pb(x),can[x] = 1;
for (int i = 0; i < pot.size(); i++) build(pot[i], i);
} else if (in_deg[b] == 3 && pot.size()) {
for (int x : pot) {
if (x != b && adj[b][x] != 1) can[x] = 0;
}
}
col(a, b);
if (pot.size() && pot[0] != -1 ) {
for (int i = 0; i < pot.size(); i++) {
if (a != pot[i] && b != pot[i] && !ff) join(a, b, i);
}
}
}
int CountCritical() {
if (!pot.size()) {
if (cnt_cyc > 1) return 0;
if (cnt_cyc == 0) return n;
if (cnt_cyc == 1) return cyc_len;
}
if (pot.size() && pot[0] == -1) {
return 0;
}
int res = 0;
for (int i = 0; i < pot.size(); i++) {
// cout<<cycles[i]<<" "<<bad_deg[i]<<" "<<can[pot[i]]<<"\n";
if (!can[pot[i]]) continue;
if (!cycles[i] && !bad_deg[i]) res++;
}
return res;
}
