#include <bits/stdc++.h>
#define ll long long
#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;
map<ll,bool>m[MAXN];
vector<ll>grafo[MAXN];
ll n, tim, vis[MAXN], id[MAXN], ars, nods, dif, dA, dN;
void Init(int N)
{
n=N;
}
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;
ll ans3=0;
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()
{
vector<ll>cant3(n,0);
ll res=0, ban, i, j, cant=0;
ll cuat=0, pos;
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;
tim=0;
memset(vis,0,sizeof(vis));
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,0,i))
ban=1;
}
if(cant3[pos]==cant&&ban==0)
res++;
}
else
{
tim+=2;
ll mal=0, raiz;
vector<pair<ll,ll>>subs;
for(i=0; i<n; i++)
{
if(vis[i]!=tim+1)
{
nods=0;
ars=0;
dfs2(i,-1);
ars/=2;
subs.pb({nods,ars});
if(ars>=nods)
{
mal++;
raiz=i;
dif=abs((nods-1)-ars);
dA=ars;
dN=nods;
}
}
}
if(mal==0)
{
ll ans2=0;
for(i=0; i<n; i++)
if(cant3[i]==cant)
ans2++;
return ans2;
}
if(mal>1)
return 0;
if(mal==1)
{
tim+=2;
Cant3=cant3;
ans3=0;
cal(raiz,cant,-1);
return ans3;
}
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)
{
if(m[a][b]==1)
return;
m[a][b]=1;
m[b][a]=1;
grafo[a].pb(b);
grafo[b].pb(a);
id[a]++;
id[b]++;
}
