#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 mp make_pair
#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, tim, vis[MAXN], id[MAXN], ars, nods, dA, dN, ans3;
bool dfs(ll nod, ll pad, ll prob)
{
vis[nod]=tim;
for(auto k:grafo[nod])
{
if(k==pad||k==prob||vis[k]==tim+1)
continue;
if(vis[k]==tim)
return 1;
if(dfs(k,nod,prob))
return 1;
}
vis[nod]=tim+1;
return 0;
}
void dfs2(ll nod, ll pad)
{
nods++;
vis[nod]=tim;
for(auto k:grafo[nod])
{
ars++;
if(k==pad||vis[k]>=tim)
continue;
dfs2(k,nod);
}
vis[nod]=tim+1;
}
vector<ll>cant3;
void Init(int N)
{
n = N;
tim = 0;
for (int i = 0; i < N; i++)
{
grafo[i].clear();
vis[i] = 0;
id[i] = 0;
}
s.clear();
cant3.clear();
}
void cal(ll nod, ll cant, ll pad)
{
ll aris=0;
vis[nod]=tim;
for(auto k:grafo[nod])
{
aris++;
if(k==pad||vis[k]>=tim)
continue;
cal(k,cant,nod);
}
if((dN-1)>(dA-aris)&&cant3[nod]==cant)
ans3++;
vis[nod]=tim+1;
}
int CountCritical()
{
cant3.clear();
cant3.resize(0);
cant3.resize(n,0);
tim=0;
ll res=0, ban, i, j, cant=0, cuat=0, pos, mal=0, raiz, ans2=0;
for(i=0; i<n; i++)
vis[i]=0;
ans3=0;
for(i=0; i<n; i++)
{
if(id[i]>=4)
{
cuat++;
pos=i;
}
else if(id[i]==3)
{
for(auto k:grafo[i])
cant3[k]++;
cant3[i]++;
cant++;
}
}
if(cuat>1)
return 0;
if(cuat==1)
{
tim+=2;
ban=0;
i=pos;
for(j=0; j<n; j++)
{
if(j==i)
continue;
if(vis[j]==tim+1)
continue;
if(dfs(j,-1,i))
ban=1;
}
if(cant3[pos]==cant&&ban==0)
res++;
}
else
{
tim+=2;
for(i=0; i<n; i++)
{
if(vis[i]!=tim+1)
{
nods=0;
ars=0;
dfs2(i,-1);
ars/=2;
if(ars>=nods)
{
mal++;
raiz=i;
dA=ars;
dN=nods;
}
}
}
if(mal==0)
{
for(i=0; i<n; i++)
if(cant3[i]==cant)
ans2++;
return ans2;
}
if(mal>1)
return 0;
if(mal==1&&n>=12500)
{
tim+=2;
cal(raiz,cant,-1);
return ans3;
}
else
{
for(i=0; i<n; i++)
{
tim+=2;
ban=0;
for(j=0; j<n; j++)
{
if(j==i)
continue;
if(vis[j]==tim+1)
continue;
if(dfs(j,0,i))
ban=1;
}
if(ban==0&&cant3[i]==cant)
res++;
}
}
}
return res;
}
void Link(int a, int b)
{
auto it=s.find({min(a,b),max(a,b)});
if(it!=s.end())
return;
s.insert({min(a,b),max(a,b)});
grafo[a].pb(b);
grafo[b].pb(a);
id[a]++;
id[b]++;
}
