#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define double long double
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int MAX = 1000010;
int n;
vi check_id;
struct Graph{
vi edge[MAX];
int deg[MAX];
int p[MAX], sz[MAX];
int cyc, cyclen, deg3;
void init(){
FOR(i, 0, n-1, 1){
edge[i].clear();
deg[i] = 0;
p[i] = i;
sz[i] = 1;
}
cyc = 0;
cyclen = 0;
deg3 = 0;
}
int findp(int v){
if(v == p[v]) return v;
return p[v] = findp(p[v]);
}
bool uni(int u, int v){
int pu = findp(u);
int pv = findp(v);
if(pu == pv) return 0;
if(sz[pu] > sz[pv]){
p[pv] = pu;
sz[pu] += sz[pv];
}
else{
p[pu] = pv;
sz[pv] += sz[pu];
}
return 1;
}
void add_edge(int u, int v, bool owo){
if(owo) edge[u].pb(v);
if(owo) edge[v].pb(u);
deg[u]++;
deg[v]++;
if(deg[u] == 3) deg3++;
if(deg[v] == 3) deg3++;
if(!uni(u, v) and deg3 == 0){
cyc++;
cyclen = sz[findp(u)];
}
}
};
Graph G_now, G_check[4];
void Init(int N){
n = N;
G_now.init();
}
void Link(int u, int v){
if(G_now.deg3 == 0){
G_now.add_edge(u, v, 1);
if(G_now.deg3 > 0){
if(G_now.deg[u] < G_now.deg[v]) swap(u, v);
check_id = G_now.edge[u];
check_id.pb(u);
FOR(i, 0, 3, 1){
G_check[i].init();
FOR(uu, 0, n-1, 1){
if(uu == check_id[i]) continue;
for(int vv : G_now.edge[uu]){
if(vv == check_id[i] or uu < vv) continue;
G_check[i].add_edge(uu, vv, 0);
}
}
}
}
return;
}
if(G_now.deg3 > 0){
FOR(i, 0, 3, 1){
if(u != check_id[i] and v != check_id[i]){
G_check[i].add_edge(u, v, 0);
}
}
}
}
int CountCritical(){
if(G_now.deg3 == 0){
if(G_now.cyc == 0) return n;
else if(G_now.cyc == 1) return G_now.cyclen;
else return 0;
}
else{
int ret = 0;
FOR(i, 0, 3, 1){
if(G_check[i].cyc == 0 and G_check[i].deg3 == 0) ret++;
}
return ret;
}
}
