#include <bits/stdc++.h>
using namespace std;
int N;
int p[1000005];
int cyc = 0;
set<int> adj[1000005];
set<int> pos, t;
int find(int v){
if(v == p[v]) return v;
return p[v] = find(p[v]);
}
bool merge(int v, int u){
v = find(v);
u = find(u);
if(v == u) return 1;
p[v] = u;
return 0;
}
void Init(int N_) {
N = N_;
for(int i = 0; i < N; i++){
p[i] = i;
pos.insert(i);
}
}
bool in[1000005];
int lol, q;
int dfs(int v){
if(pos.count(v))
t.insert(v);
if(lol != v && adj[v].count(q)){
return 1;
}
for(int x : adj[v]){
if(!in[x]){
in[x] = 1;
if(dfs(x) == 1) return 1;
}
}
if(t.count(v))
t.erase(v);
return 0;
}
void Link(int v, int u) {
if(pos.empty()) return;
adj[v].insert(u);
adj[u].insert(v);
if(adj[v].size() > 3){
if(pos.count(v)){
pos = {v};
} else {
pos.clear();
}
} else if(adj[v].size() == 3){
for(int x : adj[v]){
if(pos.count(x)) t.insert(x);
}
if(pos.count(v)) t.insert(v);
swap(pos, t);
t.clear();
}
if(adj[u].size() > 3){
if(pos.count(u)){
pos = {u};
} else {
pos.clear();
}
} else if(adj[u].size() == 3){
for(int x : adj[u]){
if(pos.count(x)) t.insert(x);
}
if(pos.count(u)) t.insert(u);
swap(pos, t);
t.clear();
}
if(merge(v, u) == 0) return;
cyc++;
if(cyc >= 3){
pos.clear();
return;
}
memset(in, 0, sizeof in);
if(pos.count(v))
t.insert(v);
if(pos.count(u))
t.insert(u);
lol = u;
q = v;
in[v] = 1;
in[u] = 1;
dfs(u);
swap(t, pos);
t.clear();
}
int CountCritical() {
return pos.size();
}
