#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;
vector<ll>grafo[MAXN];
map<ll,bool>m[MAXN];
ll n, id[MAXN], tim, vis[MAXN];
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;
}
bool ciclo(ll nod)
{
tim+=2;
for(auto k:grafo[nod])
{
if(dfs(k,nod,nod))
return 1;
}
return 0;
}
int CountCritical()
{
ll cuat=0, pos, cant=0, i;
vector<ll>can(n,0),cant3(n,0);
for(i=0; i<n; i++)
vis[i]=0;
tim=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)
{
if(cant3[pos]==cant&&ciclo(pos)==0)
return 1;
else
return 0;
}
ll ans=0;
for(i=0; i<n; i++)
{
if(cant3[i]==cant&&ciclo(i)==0)
ans++;
}
return ans;
}
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]++;
}
