#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,p[1000005],r[1000005],lst=-1,deg[1000005];
vector<int> adj[1000005],br;
vector<pii> edge;
set<int> ans;
bool nope=false;
vector<int> st;
void dfs(int x, int par, int tar) {
st.push_back(x);
for (auto s : adj[x]) {
if (s==par) continue;
if (s==tar) for (auto h : st) br.push_back(h);
else dfs(s,x,tar);
}
st.pop_back();
}
int find(int x) {
while (x!=p[x]) x=p[x];
return x;
}
void unite(int a, int b) {
a=find(a); b=find(b);
if (r[a]<r[b]) swap(a,b);
p[b]=a;
if (r[a]==r[b]) ++r[a];
}
void Init(int N_) {
n=N_;
for (int i=0; i<n; ++i) ans.insert(i), p[i]=i;
}
void add(vector<int> x) {
set<int> temp;
for (auto s : x) if (ans.find(s)!=ans.end()) temp.insert(s);
swap(temp,ans);
}
void Link(int A, int B) {
if (nope) return;
if (lst==-1) {
if (find(A)==find(B)) {
br.clear();
dfs(A,-1,A);
add(br);
} else unite(A,B);
adj[A].push_back(B);
adj[B].push_back(A);
edge.push_back(pii(A,B));
if (adj[A].size()==3) add({adj[A][0],adj[A][1],adj[A][2],A});
else if (adj[A].size()>=4) add({A});
if (adj[B].size()==3) add({adj[B][0],adj[B][1],adj[B][2],B});
else if (adj[B].size()>=4) add({B});
if (ans.size()==0) nope=true;
if (ans.size()==1) {
lst=*(ans.begin());
for (int i=0; i<n; ++i) p[i]=i;
for (auto s : edge) {
if (s.first!=lst && s.second!=lst) {
++deg[s.first]; ++deg[s.second];
unite(s.first,s.second);
}
}
}
} else {
if (A!=lst && B!=lst) {
++deg[A];
++deg[B];
if (deg[A]>2 || deg[B]>2 || find(A)==find(B)) nope=true;
unite(A,B);
}
}
}
int CountCritical() {
if (nope) return 0;
return ans.size();
}
