#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 1e6+10;
int phase;
int N;
bool initflag = false;
struct DSU{
int cnt[mxn][4];//deg = 0,deg = 1,deg = 2,deg>2
int dsu[mxn],sz[mxn],deg[mxn];
int good,cycle;
int WA = false;
void init(int n){
good = true;
cycle = -1;
for(int i = 0;i<n;i++){
dsu[i] = i,sz[i] = 1;
memset(cnt[i],0,sizeof(cnt[i]));
cnt[i][0] = 1;
}
return;
}
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void check(int a){
a = root(a);
if(cnt[a][3])good = false,cycle = -1;
else if(!cnt[a][1]&&cycle != -1)WA = true;
else if(!cnt[a][1])cycle = a;
return;
}
void del(int k){
int r = root(k);
cnt[r][min(deg[k],3)]--;
return;
}
void add(int k){
int r = root(k);
cnt[r][min(deg[k],3)]++;
return;
}
void add_edge(int a,int b){
del(a);deg[a]++;add(a);
del(b);deg[b]++;add(b);
a = root(a),b = root(b);
if(a != b){
if(sz[a]<sz[b])swap(a,b);
dsu[b] = a;
sz[a] += sz[b];
for(int i = 0;i<4;i++)cnt[a][i] += cnt[b][i];
}
check(a);
return;
}
};
vector<pii> edges;
namespace PHASE1{
DSU dsu;
void INIT(){
//cerr<<"PHASE 1 init!"<<endl;
dsu.init(N);
//cerr<<"PHASE 1 INIT DONE!"<<endl;
}
void ADD(int a,int b){
//cerr<<"PHASE 1 add: "<<a<<','<<b<<endl;
dsu.add_edge(a,b);
if(!dsu.good){
phase = 2;
initflag = true;
}
//cerr<<"PHASE 1 add done!"<<endl;
return;
}
int CALC(){
//cerr<<"PHASE 1 CALC"<<endl;
if(dsu.WA)return 0;
if(dsu.cycle != -1)return dsu.sz[dsu.root(dsu.cycle)];
else return N;
}
}
namespace PHASE2{
struct GRAPH{
DSU dsu;
int ban;
GRAPH(int k = -1){
ban = k;
dsu.init(N);
}
void add_edge(int a,int b){
if(a == ban||b == ban)return;
dsu.add_edge(a,b);
//cerr<<"ADD_EDGE: "<<ban<<','<<a<<' '<<b<<':'<<dsu.cycle<<endl;
return;
}
bool isgood(){
return dsu.good&&dsu.cycle == -1;
}
};
GRAPH v[5];
int ptr = 0;
void INIT(){
//cerr<<"PHASE 2 INIT!"<<endl;
//cerr<<"PHASE 2 INIT!"<<endl;
int fat = -1;
ptr = 0;
for(int i = 0;i<N;i++)if(PHASE1::dsu.deg[i] >= 3)fat = i;
assert(fat != -1);
v[ptr++].ban = fat;
for(auto &i:edges){
if(i.fs == fat)v[ptr++].ban = i.sc;
if(i.sc == fat)v[ptr++].ban = i.fs;
}
for(int i = 0;i<ptr;i++)v[i].dsu.init(N);
//cerr<<"SPECIALS: ";for(int i = 0;i<ptr;i++)cerr<<v[i].ban<<' '<<v[i].dsu.cycle<<',';cerr<<endl;
for(auto &i:edges){
for(int j = 0;j<ptr;j++)v[j].add_edge(i.fs,i.sc);
}
//cerr<<"SPECIALS: ";for(int i = 0;i<ptr;i++)cerr<<v[i].ban<<' '<<v[i].dsu.cycle<<',';cerr<<endl;
//cerr<<"PHASE 2 INIT DONE!"<<endl;
}
void ADD(int a,int b){
//cerr<<"PHASE 2 ADD: "<<a<<','<<b<<endl;
for(int i = 0;i<ptr;i++)v[i].add_edge(a,b);
//cerr<<"PHASE 2 ADD DONE!"<<endl;
return;
}
int CALC(){
//cerr<<"PHASE 2 CALC"<<endl;
if(PHASE1::dsu.WA)return 0;
int ans = 0;
for(int i = 0;i<ptr;i++)ans += v[i].isgood();
return ans;
}
}
void Init(int N_) {
edges.clear();
phase = 1;
N = N_;
PHASE1::INIT();
}
void Link(int A, int B) {
edges.push_back(pii(A,B));
if(phase == 1)PHASE1::ADD(A,B);
else PHASE2::ADD(A,B);
if(initflag){
//cerr<<"PHASE 2 INIT!"<<endl;
PHASE2::INIT();
initflag = false;
}
return;
}
int CountCritical() {
if(phase == 1)return PHASE1::CALC();
else return PHASE2::CALC();
}
