#include<bits/stdc++.h>
using namespace std;
vector<int> p;
bool ol = false;
int n, nc;
vector<int> deg;
unordered_set<int> s, cycle;
vector<vector<int>> g;
int ufind(int a){
if (a == p[a]) return p[a];
return p[a] = ufind(p[a]);
}
void merge(int a, int b){
a = ufind(a);
b = ufind(b);
if (a == b) return;
p[b] = a;
}
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 Init(int N) {
n = N;
nc = -1;
deg.resize(n, 0);
g.resize(n);
for (int i=0; i<n; i++){
s.insert(i);
g[i].push_back(i);
p.push_back(i);
}
return;
}
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();
return;
}
}
if (deg[B] == 4){
if (s.find(B) != s.end()){
s.clear();
s.insert(B);
}
else {
s.clear();
return;
}
}
if (deg[A] == 3){
unordered_set<int> s2;
if (s.find(B) != s.end()) s2.insert(B);
for (int x : g[A]){
if (s.find(x) != s.end()) s2.insert(x);
}
s = s2;
}
if (s.empty()) return;
if (deg[B] == 3){
unordered_set<int> s2;
if (s.find(A) != s.end()) s2.insert(A);
for (int x : g[B]){
if (s.find(x) != s.end()) s2.insert(x);
}
s = s2;
}
if (s.empty()) return;
if (ufind(A) == ufind(B)){
if (ol){
s.clear();
return;
}
if (nc == -1){
cycle.clear();
path(A, B);
for (int x : s){
if (cycle.find(x) == cycle.end()) s.erase(x);
}
if (s.empty()) return;
nc = 0;
}
else if (nc == 0){
cycle.clear();
path(A, B);
for (int x : s){
if (cycle.find(x) == cycle.end()) s.erase(x);
}
nc = -2;
if (s.empty()) return;
}
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 (i == j) continue;
if (j == *s.begin()) continue;
merge(i, j);
}
}
}
return;
}
int CountCritical() {
return s.size();
}
