#include "rings.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define SZ(x) int(x.size())
const int MXN = 1e6+5;
int n;
struct DSU {
int par[MXN], sz[MXN], deg[MXN];
bool bad, lst;
DSU() {
iota(par, par+n, 0);
fill(sz, sz+n, 1);
fill(deg, deg+n, 0);
bad = 0;
lst = 0;
}
int find(int v) { return v==par[v] ? v : par[v]=find(par[v]); }
bool add(int u, int v) {
int uu = find(u), vv = find(v);
if(lst) {
if(uu==vv) return 1;
}
else if(bad || deg[u]==2 || deg[v]==2 || uu==vv) {
bad = 1;
return uu==vv;
}
deg[u]++;
deg[v]++;
if(sz[uu]<sz[vv]) swap(uu, vv);
sz[par[vv]=uu] += sz[vv];
return 0;
}
} dsu[5];
void Init(int n) {
::n = n;
for(int i=0; i<5; i++) dsu[i] = DSU();
dsu[4].lst = 1;
}
bool step2;
int ver[4], cyc_size, cnt_cyc;
vector<int> g[MXN];
void add(int i, int u, int v) {
if(u==ver[i] || v==ver[i]) return;
dsu[i].add(u, v);
}
void gostep2() {
step2 = 1;
for(int i=0; i<4; i++)
for(int u=0; u<n; u++)
for(int v : g[u])
if(u<v)
add(i, u, v);
}
void Link(int u, int v) {
if(step2) {
for(int i=0; i<4; i++)
add(i, u, v);
}
else {
g[u].push_back(v);
g[v].push_back(u);
if(SZ(g[u])==3) {
ver[0] = u;
for(int i=0; i<3; i++)
ver[i+1] = g[u][i];
gostep2();
}
else if(SZ(g[v])==3) {
ver[0] = v;
for(int i=0; i<3; i++)
ver[i+1] = g[v][i];
gostep2();
}
else {
if(dsu[4].add(u, v)) {
cyc_size = dsu[4].sz[dsu[4].find(u)];
cnt_cyc++;
}
}
}
}
int CountCritical() {
if(step2) {
int ans = 0;
for(int i=0; i<4; i++)
if(!dsu[i].bad)
ans++;
return ans;
}
if(!cnt_cyc) return n;
if(cnt_cyc==1) return cyc_size;
return 0;
}
