#define L 1<<20
#include<bits/stdc++.h>
using namespace std;
struct union_find{
int par[L],sz[L];
union_find(){
memset(par,0,sizeof par);
for(auto&i:sz)i=1;
}
int abp(int n){
return par[n]?par[n]=abp(par[n]):n;
}
bool merge(int a,int b){
a=abp(a);b=abp(b);
if(a-b) par[a]=b,
sz[b]+=sz[a];
return a-b;
}
} global;
struct whatthehellisthis{
union_find a_union_find;
int ok,deg[L];
whatthehellisthis(){ok=1;memset(deg,0,sizeof deg);}
void AE(int a,int b){
ok&=a_union_find.merge(a,b);
ok&=max(++deg[a],++deg[b])<3;
}
} thgy[4];
int N,FAIL,deg[L];
vector<int>adj[L];
int stage2,cycsz;
int mp[L];
vector<pair<int,int>>sofar;
set<int>st;
void Init(int N_) {
N = N_;
cycsz=N;
}
int C;
void Link(int A, int B) {
if(stage2){ for(auto i:st)
if(A-i&&B-i) thgy[mp[i]].AE(A,B);
}else {
sofar.push_back({A,B});
deg[A]++; deg[B]++;
adj[A].push_back(B);
adj[B].push_back(A);
if(deg[A]>deg[B])
swap(A,B);
if(deg[B]==3){
stage2=1;
st.insert(B);
for(auto i:adj[B])
st.insert(i),mp[i]=++C;
for(auto i:st) for(auto[x,y]:sofar)
if(i-x&&i-y) thgy[mp[i]].AE(x,y);
} else if(!global.merge(A,B)){
if(cycsz-N) FAIL=1;
else cycsz=global.sz[global.abp(A)];
}
}
}
int CountCritical() {
if(FAIL)return 0;
if(stage2){
int ans=0;
for(auto i:st)
ans+=thgy[mp[i]].ok;
return ans;
} else return cycsz;
}
