#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int n, m, ok;
pair<int,int> e[maxn];
int cyc, cysz, head0[maxn], deg0[maxn], sz0[maxn];
int ban[5], bad[5], head[5][maxn], deg[5][maxn];
void Init(int _n) {
n = _n;
for(int i=1;i<=n;++i) head0[i] = i, sz0[i] = 1;
for(int k=1;k<=4;++k) {
for(int i=1;i<=n;++i) head[k][i] = i;
}
}
int CountCritical() {
if(!ok) {
if(cyc==0) return n;
if(cyc==1) return cysz;
return 0;
}
else {
int res = 0;
for(int i=1;i<=4;i++) res += !bad[i];
return res;
}
}
int findhead(int k, int x) {
if(head[k][x]==x) return x;
return head[k][x] = findhead(k, head[k][x]);
}
int findhead0(int x) {
if(head0[x]==x) return x;
return head0[x] = findhead0(head0[x]);
}
void edge(int k, int u, int v) {
if(ban[k]==u || ban[k]==v) return ;
++deg[k][u]; ++deg[k][v];
if(deg[k][u]==3) bad[k] = 1;
if(deg[k][v]==3) bad[k] = 1;
int x = findhead(k,u), y = findhead(k,v);
if(x==y) bad[k] = 1;
else head[k][x] = y;
}
void edge0(int u, int v) {
++deg0[u]; ++deg0[v];
int x = findhead0(u), y = findhead0(v);
if(x==y) {
++cyc;
cysz = sz0[x];
}
else {
sz0[y] += sz0[x];
head0[x] = y;
}
}
void build(int x) {
ok = 1;
int cur = 0;
ban[++cur] = x;
for(int i=1;i<=m;++i) {
if(e[i].first==x) ban[++cur] = e[i].second;
if(e[i].second==x) ban[++cur] = e[i].first;
}
for(int i=1;i<=m;++i) {
for(int k=1;k<=4;++k) edge(k,e[i].first,e[i].second);
}
}
void Link(int x, int y) {
++x; ++y;
e[++m] = {x,y};
if(!ok) {
edge0(x,y);
if(deg0[x]==3) build(x);
else if(deg0[y]==3) build(y);
}
else {
for(int k=1;k<=4;++k) edge(k,x,y);
}
}
