#include"bits/stdc++.h"
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)(a);++i)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
struct UnionFind{
int n;
vector<int>par;
vector<int>deg;
int ma,cycle,del;
UnionFind(){}
UnionFind(int n_):n(n_),par(n_+1,-1),deg(n_,0),ma(0),cycle(-1),del(-1){par[n]=0;}
int root(int v){return (par[v]<0?v:par[v]=root(par[v]));}
void merge(int u,int v){
if(u==del||v==del||ma>2)return;
chmax(ma,++deg[u]);
chmax(ma,++deg[v]);
u=root(u),v=root(v);
if(u==v){
cycle=(cycle<0?u:n);
return;
}
if(par[u]>par[v])swap(u,v);
par[u]+=par[v];
par[v]=u;
}
void set_del(int d){del=d;}
int get()const{
if(ma>2)return 0;
if(cycle<0)return n;
return par[cycle];
}
};
UnionFind uf[5];
vector<vector<int>>g;
vector<pair<int,int>>edge;
bool f=false;
int n;
void Init(int N_) {
n=N_;
rep(i,5)uf[i]=UnionFind(n);
g.resize(N_);
}
void Link(int A, int B) {
edge.eb(A,B);
g[A].eb(B);
g[B].eb(A);
if(!f){
uf[0].merge(A,B);
if(uf[0].ma>2){
int id=0;
rep(i,n)if(g[i].size()==3)id=i;
uf[1].set_del(id);
int idx=2;
for(auto e:g[id])uf[idx++].set_del(e);
f=true;
for(auto [a,b]:edge)rep(j,4)uf[j+1].merge(a,b);
}
}
else{
rep(i,4)uf[i+1].merge(A,B);
}
}
int CountCritical() {
if(f){
int ans=0;
rep(i,4)if(uf[i+1].get()>0)ans++;
return ans;
}
return abs(uf[0].get());
}
