#include <bits/stdc++.h>
#define ll int
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define fr first
#define se second
using namespace std;
const int MAXN = 1e6 + 1;
set<pair<ll,ll>> s;
vector<ll> grafo[MAXN];
ll n;
int vis[MAXN], id[MAXN];
vector<ll> cant3;
ll nods, ars, dA, dN, ans3;
// DFS para detección de ciclo ignorando 'pad' y 'prob'
bool dfs(int nod, int pad, int prob) {
vis[nod] = 1; // en recursión
for (int k : grafo[nod]) {
if (k == pad || k == prob || vis[k] == 2) continue;
if (vis[k] == 1) return true;
if (dfs(k, nod, prob)) return true;
}
vis[nod] = 2; // totalmente procesado
return false;
}
// DFS para contar nodos (nods) y aristas (ars) en componente
void dfs2(int nod, int pad) {
nods++;
vis[nod] = 1;
for (int k : grafo[nod]) {
ars++;
if (k == pad || vis[k]) continue;
dfs2(k, nod);
}
vis[nod] = 2;
}
// DFS para el cálculo de ans3 en la fase raíz
void cal(int nod, ll cant, int pad) {
ll aris = 0;
vis[nod] = 1;
for (int k : grafo[nod]) {
aris++;
if (k == pad || vis[k]) continue;
cal(k, cant, nod);
}
if ((dN - 1) > (dA - aris) && cant3[nod] == cant)
ans3++;
vis[nod] = 2;
}
void Init(int N) {
n = N;
s.clear();
cant3.clear();
cant3.resize(n, 0);
for (int i = 0; i < n; i++) {
grafo[i].clear();
vis[i] = 0;
id[i] = 0;
}
}
// Cuenta los nodos críticos según la lógica original, pero reinicializando vis[]
int CountCritical() {
// Limpiamos marcas de visita
for (int i = 0; i < n; i++) vis[i] = 0;
ll res = 0, cant = 0, cuat = 0, pos = -1, mal = 0, raiz = -1, ans2 = 0;
ans3 = 0;
// Recalculamos cant3 y contamos cuántos id>=4
fill(cant3.begin(), cant3.end(), 0);
for (int i = 0; i < n; i++) {
if (id[i] >= 4) {
cuat++;
pos = i;
} else if (id[i] == 3) {
cant++;
for (int k : grafo[i])
cant3[k]++;
cant3[i]++;
}
}
if (cuat > 1) return 0;
if (cuat == 1) {
// Caso único con grado>=4
// Comprobamos ciclo al remover pos
for (int j = 0; j < n; j++) {
if (j == pos) continue;
if (!vis[j]) {
if (dfs(j, -1, pos))
return 0;
}
}
if (cant3[pos] == cant)
res = 1;
return res;
} else {
// Sin nodos de grado>=4: buscamos componente “mala”
for (int i = 0; i < n; i++) {
if (!vis[i]) {
nods = ars = 0;
dfs2(i, -1);
ars /= 2;
if (ars >= nods) {
mal++;
raiz = i;
dA = ars;
dN = nods;
}
}
}
if (mal == 0) {
// Ninguna componente con aristas>=nodos
for (int i = 0; i < n; i++)
if (cant3[i] == cant)
ans2++;
return ans2;
}
if (mal > 1) return 0;
// Una sola componente “mala”: recalculamos ans3
for (int i = 0; i < n; i++) vis[i] = 0;
cal(raiz, cant, -1);
return ans3;
}
}
void Link(int a, int b) {
auto e = make_pair(min(a,b), max(a,b));
if (s.count(e)) return;
s.insert(e);
grafo[a].pb(b);
grafo[b].pb(a);
id[a]++;
id[b]++;
}
