#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)(x.size())
#define fi first
#define se second
const int MX = (int)(1e6+3);
typedef pair<int,int> ii;
int N,deg[6][MX],p[6][MX],s[6][MX],pot[4],k,len;
vector<int> vec[MX],G;
vector<ii> edges;
multiset<int,greater<int> > myset;
bool flag2,flag3,flag4,st,cycle,ok[5];
bitset<MX> vis;
void Init(int N_) {
N = N_;
for (int j = 0; j < 6; ++j)
for (int i = 0; i < N; ++i)
p[j][i]=i,s[j][i]=1;
}
int findSet(int idx,int i){
if(p[idx][i]==i)return i;
return p[idx][i]=findSet(idx,p[idx][i]);
}
bool Union(int idx,int a,int b){
a=findSet(idx,a),b=findSet(idx,b);
if(a==b)return 0;
if(s[idx][a]>s[idx][b])swap(a,b);
p[idx][a]=b,s[idx][b]+=s[idx][a];
return 1;
}
void dfs(int node,int par){
vis[node]=1;G.pb(node);
for(auto it:vec[node]){
if(len)return;
if(it!=par){
if(vis[it]){
len=sz(G);
return;
}
dfs(it,node);
}
}
G.pop_back();
}
void Link(int A, int B) {
if(st)return;
edges.pb({A,B});
vec[A].pb(B),vec[B].pb(A);
deg[0][A]++,deg[0][B]++;
if(!flag3 && !flag4){
bool h=Union(0,A,B);
if(!h && cycle){st=1;return;}
else if(!h){cycle=1;dfs(A,A);}
}
if(flag3){
for (int i = 0; i < 4; ++i){
if(A==pot[i] || B==pot[i])continue;
if(!Union(i+1,A,B))ok[i]=0;
deg[i+1][A]++,deg[i+1][B]++;
if(deg[i+1][A]>=3 || deg[i+1][B]>=3)ok[i]=0;
}
}
if(k!=A && k!=B && flag4){
if(!Union(5,A,B)){st=1;return;}
deg[5][A]++,deg[5][B]++;
if(deg[5][A]>=3 || deg[5][B]>=3){st=1;return;}
}
if(!flag4 && (deg[0][A]==3 || deg[0][B]==3) && (deg[0][A]<=3) && (deg[0][B]<=3) && !flag3){
flag3=1;
if(deg[0][A]!=3)swap(A,B);
vec[A].pb(A);
for (int i = 0; i < 4; ++i){
bool f=1;
pot[i]=vec[A][i];
for(auto it:edges){
if(it.fi!=vec[A][i] && it.se!=vec[A][i]){
if(!Union(i+1,it.fi,it.se)){f=0;break;}
deg[i+1][it.fi]++,deg[i+1][it.se]++;
if(deg[i+1][it.fi]>=3 || deg[i+1][it.se]>=3){f=0;break;}
}
}
ok[i]=f;
}
vec[A].pop_back();
}
else if(deg[0][A]>=4 || deg[0][B]>=4){
if(deg[0][A]>=4 && deg[0][B]>=4)st=1;
else{
if(deg[0][A]<4)swap(A,B);
if(A==k)return;
flag4=1,flag3=0,k=A;
bool f=1;
for(auto it:edges)
if(it.fi!=A && it.se!=A){
if(!Union(5,it.fi,it.se)){f=0;break;}
deg[5][it.fi]++,deg[5][it.se]++;
if(deg[5][it.fi]>=3 || deg[5][it.se]>=3){f=0;break;}
}
if(!f)st=1;
}
}
}
int CountCritical() {
if(st)return 0;
if(!flag3 && !flag4){
if(!cycle)return N;
else return len;
}
if(flag3)return ok[0]+ok[1]+ok[2]+ok[3];
if(flag4)return 1;
return -1;
}
