#include<bits/stdc++.h>
using namespace std;
vector<int> p;
int find(int a){
if (a == p[a]) return p[a];
return p[a] = find(p[a]);
}
void merge(int a, int b){
a = find(a);
b = find(b);
if (a == b) return;
p[b] = a;
}
bool ol = false;
int n, nc;
vector<int> deg;
unordered_set<int> s, cycle;
vector<vector<int>> g;
void Init(int N) {
n = N;
nc = -1;
deg.resize(n, 0);
for (int i=0; i<n; i++){
s.insert(i);
g.push_back({i});
p.push_back(i);
}
}
void path(int a, int b){
vector<int> par(n, -1);
par[a] = a;
queue<int> q;
q.push(a);
while (!q.empty()){
int cur = q.front();
q.pop();
if (cur == b){
cycle.insert(b);
while (cur != a){
cycle.insert(par[cur]);
cur = par[cur];
}
return;
}
for (int next : g[cur]){
if (par[next] == -1 && next != cur){
par[next] = cur;
q.push(next);
}
}
}
}
void Link(int A, int B){
if (s.empty()) return;
deg[A]++;
deg[B]++;
if (deg[A] == 4){
if (s.find(A) != s.end()){
s.clear();
s.insert(A);
}
else s.clear();
}
if (deg[B] == 4){
if (s.find(B) != s.end()){
s.clear();
s.insert(B);
}
else s.clear();
}
if (deg[A] == 3){
for (int x : s){
if (count(g[A].begin(), g[A].end(), x) == 0) s.erase(x);
}
}
if (deg[B] == 3){
for (int x : s){
if (count(g[B].begin(), g[B].end(), x) == 0) s.erase(x);
}
}
if (s.empty()) return;
if (find(A) == find(B)){
if (ol){
s.clear();
return;
}
if (nc == -1){
cycle.clear();
path(A, B);
/*for (int x : cycle) cout << x << " ";
cout << endl;*/
for (int x : s){
if (cycle.find(x) == cycle.end()) s.erase(x);
}
if (s.empty()) return;
nc = find(A);
}
else if (nc >= 0){
if (find(A) != nc){
s.clear();
return;
}
cycle.clear();
path(A, B);
for (int x : s){
if (cycle.find(x) == cycle.end()) s.erase(x);
}
nc = -2;
}
else if (nc == -2){
if (s.size() != 1){
s.clear();
return;
}
}
}
if (s.empty()) return;
if (!ol || (A != *s.begin() && B != *s.begin())) merge(A, B);
g[A].push_back(B);
g[B].push_back(A);
if (s.size() == 1 && !ol){
ol = true;
for (int i=0; i<n; i++) p[i] = i;
for (int i=0; i<n; i++){
if (i == *s.begin()) continue;
for (int j : g[i]){
if (j == *s.begin()) continue;
merge(i, j);
}
}
}
}
int CountCritical() {
return s.size();
}
