#include <bits/stdc++.h>
using namespace std;
#define PB push_back
int n,par[3][1000005],v1=-1,v2=-1,ins,rps,ino[1000005],rpo[1000005],in[1000005],ts,ans,nx[1000005],vis[1000005],fr=-1,tr[1000005],trs;
bool zr,rpt,rpt2,ok1,ok2;
vector<int>g[1000005];
int find(int q,int x){
if(par[q][x]==x)return x;
return par[q][x]=find(q,par[q][x]);
}
bool same(int q,int x,int y){
return find(q,x)==find(q,y);
}
int unit(int q,int x,int y){
par[q][find(q,y)]=find(q,x);
}
void Init(int N){
n=N;
for(int i=0;i<n;i++)par[0][i]=i,par[1][i]=i,par[2][i]=i,nx[i]=-1;
ans=n;
}
void check(int v){
if(ino[v]==ins&&rpo[v]==rps)ans++;
}
void up(int v){
in[v]++;
if(in[v]==3){
trs++;
tr[v]++;
for(int i=0;i<g[v].size();i++)tr[g[v][i]]++;
ans=0;
ins++;
if(fr!=-1){
if(tr[fr]==trs){
ino[fr]=ins;
check(fr);
}
}else{
if(tr[v]==trs)ino[v]=ins;
check(v);
for(int i=0;i<g[v].size();i++){
int u=g[v][i];
if(tr[u]==trs)ino[u]=ins;
check(u);
}
}
}else if(in[v]==4){
if(fr==-1){
fr=v;
if(tr[v]==trs){
ins++;
ino[v]=ins;
ans=0;
check(v);
}else zr=true;
}else zr=true;
}
}
void dfs1(int v,int p){
nx[v]=p;
for(int i=0;i<g[v].size();i++){
if(g[v][i]!=p)dfs1(g[v][i],v);
}
}
void Link(int a,int b){
if(zr)return;
if(rpt2){
ans=0;
rps++;
if(same(1,a,b))ok1=false;
if(same(2,a,b))ok2=false;
if(v1!=a&&v1!=b)unit(1,a,b);
if(v2!=a&&v2!=b)unit(2,a,b);
if(ok1)rpo[v1]=rps;
if(ok2)rpo[v2]=rps;
check(v1);
if(v2!=-1)check(v2);
}else if(!same(0,a,b)){
unit(0,a,b);
if(nx[b]==-1)swap(a,b);
if(nx[a]==-1&&nx[b]!=-1)dfs1(a,b);
}else{
if(!rpt){
rpt=true;
dfs1(a,a);
ans=0;
rps++;
int v=b;
while(1){
vis[v]=rps;
rpo[v]=rps;
check(v);
if(v==a)break;
v=nx[v];
}
}else{
rpt2=true;
if(nx[a]==-1||nx[b]==-1)zr=true;
else{
ans=0;
rps++;
int v=a,u=b;
while(vis[v]==0){
vis[v]=rps;
v=nx[v];
}
while(vis[u]==0){
vis[u]=rps;
u=nx[u];
}
if(vis[u]==rps)zr=true;
if(rpo[v]==rps-1)rpo[v]=rps,ok1=true;
check(v);
v1=v;
if(v!=u){
v2=u;
if(rpo[u]==rps-1)rpo[u]=rps,ok2=true;
check(u);
}
if(v1!=-1){
for(int i=0;i<n;i++){
for(int j=0;j<g[i].size();j++){
if(i!=v1&&g[i][j]!=v1)unit(1,i,g[i][j]);
}
}
}
if(v2!=-1){
for(int i=0;i<n;i++){
for(int j=0;j<g[i].size();j++){
if(i!=v2&&g[i][j]!=v2)unit(2,i,g[i][j]);
}
}
}
}
}
}
g[a].PB(b);
g[b].PB(a);
up(a);
up(b);
}
int CountCritical() {
if(zr)return 0;
return ans;
}
