#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e6 + 10;
vector<int> g[mxn], deg(mxn), ldr(mxn), rnk(mxn), cycle(mxn), LDR(mxn), RNK(mxn);
set<int> S[mxn], act, hasCycle;
set<pair<int, int>> edg;
multiset<int> vals;
int N, mx, cnt, cycles, foundX = -1, foundY = -1;
int FIND(int x) {
if (x == LDR[x]) return x;
return LDR[x] = FIND(LDR[x]);
}
void UNION(int x, int y) {
x = FIND(x), y = FIND(y);
if (x == y) return;
if (RNK[y] > RNK[x]) swap(x, y);
RNK[x] += RNK[y];
LDR[y] = x;
}
int Find(int x) {
if (x == ldr[x]) return x;
return ldr[x] = Find(ldr[x]);
}
void Union(int x, int y) {
x = Find(x), y = Find(y);
if (x == y) cycles++, cycle[x]++, hasCycle.insert(x);
else {
if (rnk[y] > rnk[x]) swap(x, y);
ldr[y] = x;
act.erase(y);
if (hasCycle.count(y)) hasCycle.erase(y);
rnk[x] += rnk[y];
cycle[x] += cycle[y];
if (cycle[x]) hasCycle.insert(x);
}
}
void Init(int N_) {
N = N_;
for (int i = 0; i < N; i++) S[0].insert(i), ldr[i] = i, LDR[i] = i, RNK[i] = 1, rnk[i] = 1, act.insert(i), vals.insert(0);
}
void Link(int A, int B) {
Union(A, B);
if (foundX != -1 && A != foundX && A != foundY && B != foundX && B != foundY) UNION(A, B);
S[deg[A]].erase(A);
S[deg[B]].erase(B);
vals.erase(vals.find(deg[A]));
vals.erase(vals.find(deg[B]));
deg[A]++, deg[B]++;
if (deg[A] == 3) cnt++;
if (deg[B] == 3) cnt++;
vals.insert(deg[A]);
vals.insert(deg[B]);
S[deg[A]].insert(A);
S[deg[B]].insert(B);
mx = max({mx, deg[A], deg[B]});
g[A].push_back(B);
g[B].push_back(A);
edg.insert({A, B});
edg.insert({B, A});
}
int CountCritical() {
if (mx < 3) {
if (cycles == 0) return N;
if (cycles > 1) return 0;
return rnk[*hasCycle.begin()];
}
if (cnt > 2) return 0;
if (cnt == 1 && cycles == 0) return 1 + deg[*S[mx].begin()];
if (cnt == 1) {
int node = *S[mx].begin();
for (auto x : hasCycle) {
if (Find(x) != Find(node)) return 0;
}
if (hasCycle.size() == 1) return 3;
return 1;
}
auto it = vals.rbegin();
--it;
if (*it > 3) return 0;
int nodeOne = *S[mx].begin(), nodeTwo = *S[*it].rbegin();
for (auto x : hasCycle) {
if (Find(x) != Find(nodeOne)) return 0;
}
if (foundX == -1) {
foundX = nodeOne, foundY = nodeTwo;
for (auto x : edg) {
if (x.first != foundX && x.first != foundY && x.second != foundX && x.second != foundY) {
UNION(x.first, x.second);
}
}
}
bool connection = edg.count({nodeOne, nodeTwo});
if (deg[nodeOne] > 3) {
if (!connection) return 0;
for (auto el : g[nodeTwo]) {
if (el == nodeOne) continue;
for (auto EL : g[nodeTwo]) {
if (el == nodeOne) continue;
if (el == EL) continue;
if (FIND(el) == FIND(EL)) return 0;
}
}
return 1;
}
vector<int> nodes;
for (auto x : g[nodeOne]) {
for (auto y : g[nodeTwo]) {
if (x == y) connection = 1, nodes.push_back(x);
}
}
if (!connection) return 0;
int ans = 0;
if (edg.count({nodeOne, nodeTwo})) {
bool flag = 1;
for (auto x : g[nodeOne]) {
if (x == nodeTwo) continue;
for (auto y : g[nodeOne]) {
if (y == nodeTwo) continue;
if (x == y) continue;
if (FIND(x) == FIND(y)) {
flag = 0;
}
}
}
ans += flag;
flag = 1;
for (auto x : g[nodeTwo]) {
if (x == nodeOne) continue;
for (auto y : g[nodeTwo]) {
if (y == nodeOne) continue;
if (x == y) continue;
if (FIND(x) == FIND(y)) {
flag = 0;
}
}
}
ans += flag;
}
for (auto x : nodes) {
bool flag = 1;
vector<int> rest;
for (auto el : g[nodeOne]) {
if (el != x) rest.push_back(el);
}
for (auto el : rest) {
for (auto EL : rest) {
if (el == EL) continue;
if (FIND(el) == FIND(EL)) flag = 0;
}
}
if (!edg.count({nodeOne, nodeTwo}) && nodes.size() == 1) rest.clear();
for (auto el : g[nodeTwo]) {
if (el != x) rest.push_back(el);
}
for (auto el : rest) {
for (auto EL : rest) {
if (el == EL) continue;
if (FIND(el) == FIND(EL)) flag = 0;
}
}
ans += flag;
}
return ans;
}
