#include<bits/stdc++.h>
using namespace std;
struct DSU{
int nbGroups =0;
bool needs_op_buffer = false;
vector<int> anc;
vector<int> sz;
vector<pair<int, pair<int, int>>> op_buffer;
int nbCycles = 0;
int szCycle= 0;
DSU(){};
DSU(int l){
anc.resize(l);
sz.resize(l);
for(int i = 0; i<l; i++){
anc[i] = i;
sz[i] = 1;
}
nbGroups = l;
}
int c(int u){
if(needs_op_buffer)op_buffer.push_back({u, {anc[u], sz[u]}});
if(anc[u] == u){
return u;
}
int v= c(anc[u]);
anc[u] =v;
return v;
}
void merge(int a, int b){
//cerr<<"merging "<<a<<" "<<b<<endl;
a = c(a);
b= c(b);
if(a==b){
nbCycles ++;
szCycle = sz[a];
return;
}
nbGroups--;
if(needs_op_buffer)op_buffer.push_back({a, {anc[a], sz[a]}});
if(needs_op_buffer)op_buffer.push_back({b, {anc[b], sz[b]}});
if(sz[a]>sz[b]){
swap(a, b);
}
anc[a] = b;
sz[b] += sz[a];
}
void undo_op(){
auto e= op_buffer.back();
if(anc[e.first] == e.first){
nbGroups--;
}
op_buffer.pop_back();
anc[e.first] = e.second.first;
sz[e.first] = e.second.second;
if(anc[e.first] == e.first){
nbGroups++;
}
}
void undo_buffer(){
while(op_buffer.size()>0){
undo_op();
}
}
};
int N;
const int MAX_N= 1e6;
vector<int> adj[MAX_N];
vector<int> interesting;
bool isInteresting[MAX_N];
int idInteresting[MAX_N];
int deg[MAX_N], oc[MAX_N];
DSU boringDSU, fullDSU;
int above3= 0;
int above4=0;
DSU recalcDSU(){
DSU newDSU(N);
for(int iV = 0; iV<N; iV++){
for(auto u: adj[iV]){
if(!(isInteresting[u] || isInteresting[iV])){
newDSU.merge(iV, u);
}
}
}
newDSU.op_buffer.clear();
return newDSU;
}
int state = 0;
//0 = only deg<=2
//1 only deg <=3, some interesting left
//2 One deg =4, some interesting
//3 no interesting left
void changeDeg(int u, int d){
if(deg[u]>=3){
above3--;
}
if(deg[u] >= 4){
above4--;
}
oc[deg[u]]--;
deg[u] +=d;
assert(deg[u]>=0);
oc[deg[u]] ++;
if(deg[u]>=3){
above3++;
}
if(deg[u] >= 4){
above4++;
}
}
void Init(int N_) {
N = N_;
fill(&oc[0], &oc[N], 0);
fill(&isInteresting[0], &isInteresting[N], true);
for(int i = 0; i<N; i++){
interesting.push_back(i);
idInteresting[i] = i;
}
oc[0] =N;
boringDSU = DSU(N);
fullDSU = DSU(N);
boringDSU.needs_op_buffer = true;
}
void updInteresting(int u, bool tolerant){
unordered_set<int> close;
if(tolerant){
for(auto e: adj[u]){
close.insert(e);
}
}
close.insert(u);
vector<int> new_interesting;
for(int i = 0; i<interesting.size(); i++){
auto it = interesting[i];
if(close.find(it) == close.end()){
isInteresting[it] = false;
//cerr<<"removing "<<*it<<endl;
for(auto ee: adj[it]){
if(!isInteresting[ee]){
boringDSU.merge(it, ee);
}
}
}
else{
idInteresting[it] =new_interesting.size();
new_interesting.push_back(it);
}
}
swap(interesting, new_interesting);
}
void recalcDeg(){
for(int i = 0; i<N; i++){
if(deg[i] < 4){
changeDeg(i, -deg[i]);
for(auto v: adj[i]){
if(deg[v] != 4){
changeDeg(i, 1);
}
}
}
}
}
int calcLinks(int l, int r){
int res= 0;
if(l == r){
int iRem = interesting[l];
for(auto e: adj[iRem]){
changeDeg(e, -1);
changeDeg(iRem, -1);
}
if((oc[0]-1)*2 + oc[1] == (boringDSU.nbGroups-1)*2 && above3 ==0) res= 1;
for(auto e: adj[iRem]){
changeDeg(e, 1);
changeDeg(iRem, 1);
}
return res;
}
int mid = (l+r)/2;
int begin_size = boringDSU.op_buffer.size();
for(int i = l; i<=mid; i++){
int iAdd =interesting[i];
for(auto e: adj[iAdd]){
if((!isInteresting[e]) || !(mid+1<=idInteresting[e] && idInteresting[e]<=r)){
boringDSU.merge(e, iAdd);
}
}
}
res += calcLinks(mid+1, r);
while(boringDSU.op_buffer.size()>begin_size){
boringDSU.undo_op();
}
for(int i = mid+1; i<=r; i++){
int iAdd =interesting[i];
for(auto e: adj[iAdd]){
if((!isInteresting[e]) || !(l<=idInteresting[e] && idInteresting[e]<=mid)){
boringDSU.merge(e, iAdd);
}
}
}
res += calcLinks(l, mid);
while(boringDSU.op_buffer.size()>begin_size){
boringDSU.undo_op();
}
return res;
}
void Link(int A, int B) {
if(interesting.size()== 0){
return;
}
fullDSU.merge(A, B);
adj[A].push_back(B);
adj[B].push_back(A);
if(deg[A] <4 && deg[B] < 4){
changeDeg(A, +1);
changeDeg(B, +1);
}
if((deg[A]== 3 || deg[B]==3)){
if(deg[A] != 3){
swap(A, B);
}
updInteresting(A, true);
if(deg[B] == 3){
updInteresting(B, true);
}
}
if(isInteresting[A] || isInteresting[B]){
}
else{
boringDSU.merge(A, B);
boringDSU.op_buffer.clear();
}
if((deg[A] == 4 || deg[B]== 4) && above4 == 1){
if(deg[A] != 4){
swap(A, B);
}
updInteresting(A, false);
if(deg[B] == 4){
updInteresting(B, false);
}
recalcDeg();
}
}
int prev_res= 0;
int calc(){
if(interesting.size() == 0){
return 0;
}
else{
if(above4 == 1){
if((oc[0])*2 + oc[1] == (boringDSU.nbGroups-1)*2 && above3 ==1){
return 1;
}
return 0;
}
else if(above3>=1){
return calcLinks(0, interesting.size()-1);
}
else{
if(fullDSU.nbCycles == 0){
return N;
}
else if(fullDSU.nbCycles == 1){
return fullDSU.szCycle;
}
else{
return 0;
}
}
}
}
int CountCritical() {
//cerr<<oc[0]<<" "<<oc[1]<<" "<<oc[2]<<" "<<oc[3]<<endl;
prev_res = calc();
return prev_res;
}
