#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int pai[MAXN][5], sz[MAXN][5];
int deg[MAXN];
int good[MAXN], ciclo[5];
int ciclo_geral[MAXN], init[MAXN];
int adj[MAXN][3];
int sz_ciclo = 0;
bool ok = true;
int n;
int get(int v, int x){
if(v == pai[v][x]) return v;
return pai[v][x] = get(pai[v][x], x);
}
void dsu_union(int a, int b, int x){
a = get(a, x);
b = get(b, x);
if(sz[a][x] > sz[b][x]) swap(a, b);
pai[a][x] = b;
sz[b][x] += sz[a][x];
}
vector<pair<int, int>> edges;
vector<int> cand;
int cnt_4 = 0, cnt_3 = 0;
int cnt_ciclo = 0;
void dsu_init(int x){
if(init[cand[x]]) return;
init[cand[x]] = 1;
for(int i=0; i<n; i++) pai[i][x] = i, sz[i][x] = 1;
ciclo[x] = 0;
for(auto [a, b] : edges){
if(a == cand[x] || b == cand[x]) continue;
if(get(a, x) != get(b, x)) dsu_union(a, b, x);
else ciclo[x] = 1;
}
}
void Init(int n_){
n = n_;
ok = true;
cand.clear();
edges.clear();
for(int j=0; j<5; j++){
for(int i=0; i<n; i++) pai[i][j] = i, sz[i][j] = 1;
ciclo[j] = 0;
}
for(int i=0; i<n; i++){
deg[i] = 0;
good[i] = 1;
ciclo_geral[i] = 0;
cand.push_back(i);
}
cnt_3 = cnt_4 = cnt_ciclo = 0;
}
void check_4(int v){
assert((int) cand.size() <= 4); // passou pelo check_3 em algum momento
for(auto x : cand) if(x != v) good[x] = 0;
cand.clear();
if(good[v]){
cand.push_back(v);
dsu_init(0);
}
}
void check_3(int v){
vector<int> to_add;
if(good[v]) to_add.push_back(v);
for(int i=0; i<deg[v]; i++) if(good[adj[v][i]]) to_add.push_back(adj[v][i]);
for(auto x : cand) good[x] = 0;
cand.clear();
for(auto x : to_add){
cand.push_back(x);
good[x] = 1;
dsu_init(cand.size() - 1);
}
assert((int) cand.size() <= 4);
}
void Link(int a, int b){
if(!ok) return;
deg[a] ++, deg[b] ++;
if(deg[a] <= 3) adj[a][deg[a] - 1] = b;
if(deg[b] <= 3) adj[b][deg[b] - 1] = a;
if(deg[a] == 4) cnt_4 ++;
if(deg[b] == 4) cnt_4 ++;
if(deg[a] == 3) cnt_3 ++;
if(deg[b] == 3) cnt_3 ++;
if(cnt_4 > 1){
for(auto x : cand) good[x] = 0;
cand.clear();
ok = false;
return;
}
if(deg[a] == 4) check_4(a);
if(deg[b] == 4) check_4(b);
if(!ok) return;
if(deg[a] == 3) check_3(a);
if(deg[b] == 3) check_3(b);
// cand atualizado!
edges.push_back({a, b});
if(cnt_3 > 0){
assert((int) cand.size() <= 4);
for(int i=0; i<(int) cand.size(); i++){
if(a == cand[i] || b == cand[i]) continue;
if(get(a, i) != get(b, i)) dsu_union(a, b, i);
else ciclo[i] = 1;
}
}
if(get(a, 4) != get(b, 4)) dsu_union(a, b, 4);
else{
if(ciclo_geral[get(a, 4)] == 0) cnt_ciclo ++;
ciclo_geral[get(a, 4)] = 1;
sz_ciclo = sz[get(a, 4)][4];
}
if(cnt_ciclo > 1) ok = false;
/*cout << "after link " << a << " " << b << ", cnt_ciclo = " << cnt_ciclo << "\n";
for(int i=0; i<(int) cand.size(); i++){
cout << cand[i] << " " << ciclo[i] << "\n";
}
cout << ".\n";
*/
}
int CountCritical(){
// cout << "cnt_ciclo = " << cnt_ciclo << "\n";
if(!ok) return 0;
if(cnt_ciclo > 1) return 0;
if(cnt_3 == 0){
if(cnt_ciclo == 0) return n;
return sz_ciclo;
}
assert((int) cand.size() <= 4);
int ans = 0;
for(int i=0; i<(int) cand.size(); i++) if(!ciclo[i]) ans ++;
return ans;
}
