#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e6+5;
int N;
int cmode = 2, ans, curcyc = -1, cans = 0;
int deg[mxn];
vector<int> adj[mxn];
int par[mxn];
int fpar(int x) {return par[x] == x ? x : par[x] = fpar(par[x]);}
struct exc {
//exclude a node from graph
vector<int> deg, par;
int valid = 1;
int x, curcyc = -1;
int fpar(int x) {
return par[x] == x ? x : (par[x] = this->fpar(par[x]));
}
exc(int x):x(x) {
//excludes x from graph
deg = vector<int>(mxn, 0);
par = vector<int>(mxn, 0);
iota(par.begin(), par.end(), 0);
valid = 1;
for(int i=0;i<N && valid;i++) {
if(i == x) continue;
for(auto &e:adj[i]) {
if(e == x) continue;
if(e < i) continue;
deg[i]++; deg[e]++;
if(max(deg[i], deg[e]) > 2) {
valid = 0;
//cout << 'f';
break;
}
if(this->fpar(i) == this->fpar(e)) {
valid = 0;
//cout << i << ' ' << e;
break;
}
par[this->fpar(i)] = this->fpar(e);
}
}
}
void addedge(int a, int b) {
if(!valid) return;
if(a == x || b == x) return ;
deg[a]++; deg[b]++;
if(max(deg[a], deg[b]) > 2) {
valid = 0;
return ;
}
//cout << x << " -> " << this->fpar(a) << ' ' << this->fpar(b) << '\n';
if(this->fpar(a) == this->fpar(b)) {
valid = 0;
return ;
}
par[this->fpar(a)] = this->fpar(b);
}
};
vector<exc> checks;
void Init(int N_) {
N = N_;
cans = N;
ans = N;
for(int i=0;i<mxn;i++) par[i] = i;
}
void Link(int A, int B) {
deg[A]++; deg[B]++;
adj[A].push_back(B); adj[B].push_back(A);
if(cmode == 4) {
for(auto &e:checks) e.addedge(A, B);
} else if(cmode < max(deg[A], deg[B])) {
//change mode?!?!??! ong
cmode = max(deg[A], deg[B]);
checks.clear();
if(cmode == 3) {
for(int i=0;i<N;i++) {
if(deg[i] != 3) continue;
checks.emplace_back(exc(i));
for(auto &e:adj[i]) {
checks.emplace_back(exc(e));
}
break;
}
} else {
for(int i=0;i<N;i++) {
if(deg[i] != 4) continue;
checks.emplace_back(exc(i));
break;
}
}
} else if(cmode == 2){
if(cans == 0) return;
if(cans == N) {
if(fpar(A) == fpar(B)) {
curcyc = fpar(A);
cans = 0;
for(int i=0;i<N;i++) cans += (curcyc == fpar(i));
} else {
par[fpar(A)] = fpar(B);
}
} else {
if(fpar(A) == fpar(B)) {
if(fpar(A) != curcyc) cans = 0;
} else {
par[fpar(A)] = fpar(B);
}
}
} else {
for(auto &e:checks) e.addedge(A, B);
}
}
int CountCritical() {
if(cmode == 2) {
return cans;
} else {
int cnt = 0;
for(auto &e:checks) cnt += e.valid;
return cnt;
}
}
