#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define pii pair <int,int>
using namespace std;
const int N = 1e6 + 5;
vector <int> cycles,v[N];
vector <pii> edges;
int deg[N],n,nodes,p[N];
bool crit;
int critical[7],m,fail[7],degree[7][N];
int pp[7][N],sz[N];
void Init(int N_) {
crit=0;
n = N_;
for (int i = 0; i < n; i++)
p[i] = i,sz[i] = 1;
}
int P(int x){
if(x==p[x]) return x;
return p[x]=P(p[x]);
}
void dsu(int x,int y){
int px=P(x),py=P(y);
if (px == py){
cycles.pb(sz[px]);
return;
}
p[py] = px;
sz[px] += sz[py];
sz[py] = 0;
}
int PP(int i,int x){
if(pp[i][x] == x) return x;
return pp[i][x] = PP(i,pp[i][x]);
}
void dsuu(int i,int x,int y){
int px=PP(i,x),py=PP(i,y);
if (px == py){
fail[i] = 1;
return;
}
pp[i][py] = px;
}
void addedge(int i,int x,int y){
if (fail[i]) return;
if (x == critical[i] || y == critical[i]) return;
degree[i][x]++;
degree[i][y]++;
if (degree[i][x] > 2 || degree[i][y] > 2) {
fail[i] = 1;
return;
}
dsuu(i,x,y);
}
void Link(int A, int B) {
bool old = crit;
deg[A]++;
deg[B]++;
v[A].pb(B); v[B].pb(A);
edges.pb({A,B});
if (!crit){
if (deg[A] >= 3){
crit = 1;
if (deg[A] >= 4){
m = 1;
critical[1] = A;
} else{
m = 4;
critical[1] = A;
critical[2] = v[A][0];
critical[3] = v[A][1];
critical[4] = v[A][2];
}
}
}
if (!crit){
if (deg[B] >= 3){
crit = 1;
if (deg[B] >= 4){
m = 1;
critical[1] = B;
} else{
m = 4;
critical[1] = B;
critical[2] = v[B][0];
critical[3] = v[B][1];
critical[4] = v[B][2];
}
}
}
if (old){
for (int i = 1; i <= m; i++){
addedge(i,A,B);
}
}else if (!old && crit){
for (int i = 1; i <= m; i++){
fail[i] = 0;
for (int j = 0; j < n; j++){
pp[i][j] = j;
}
for (auto [x,y]: edges){
addedge(i,x,y);
}
}
}
if (crit) return;
dsu(A,B);
}
int CountCritical() {
if (crit){
int ans=0;
for (int i = 1; i <= m; i++){
ans += (!fail[i]);
}
return ans;
}
int ans = 0;
if (!cycles.size()) ans = n;
else if ((int)cycles.size() == 1) ans = cycles[0];
return ans;
}
