#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> edg[1000005];
int DEG3 = -1;
int DEG4 = -1;
bool choicesToggle = false;
set<int> choices, tmp;
int dsu[1000005];
int cyc[1000005];
bool vis[1000005];
int pre[1000005];
int cyccnt = 0;
int GG = 0;
vector<int> undolist;
int find(int x) {
if(dsu[x]==x)return x;
return dsu[x] = find(dsu[x]);
}
void setintersection(set<int> tmp) {
if(!choicesToggle) {
choicesToggle = true;
choices = tmp;
return;
}
set<int> tmp2;
for(int i:tmp) {
if(choices.find(i)!=choices.end()) {
tmp2.insert(i);
}
}
choices = tmp2;
}
void dfs(int x, int p, int tar) {
vis[x] = true;
pre[x] = p;
undolist.push_back(x);
if(x==tar) {
int ptr = pre[tar];
tmp.clear();
tmp.insert(tar);
while(ptr != tar) {
tmp.insert(ptr);
ptr = pre[ptr];
}
setintersection(tmp);
return;
}
for(int i:edg[x]) {
if(i==p) continue;
if(!vis[i]) dfs(i, x, tar);
}
}
void merge(int x, int y) {
if(find(x)==find(y)) {
if(cyc[find(x)]>1) GG = 1;
cyc[find(x)]++;
if(!GG) dfs(x, y, y);
for(int i:undolist) vis[i] = false;
undolist.clear();
} else {
cyc[find(x)] += cyc[find(y)];
dsu[find(y)] = find(x);
}
}
void Init(int N_) {
N = N_;
for(int i=0; i<N; i++) dsu[i] = i;
}
void Link(int A, int B) {
if(GG) return;
edg[A].push_back(B);
edg[B].push_back(A);
merge(A, B);
if(edg[A].size()==4) setintersection({A});
else if(edg[A].size()==3) setintersection({A, edg[A][0], edg[A][1], edg[A][2]});
if(edg[B].size()==4) setintersection({B});
else if(edg[B].size()==3) setintersection({B, edg[B][0], edg[B][1], edg[B][2]});
}
int CountCritical() {
if(GG) return 0;
if(!choicesToggle) return N;
else return choices.size();
}
