#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
const int LIM=1e6+7;
pair<int,int>kraw[LIM];
int F[LIM], ile[LIM], deg[LIM], n, q, typ, ans;
vector<int>kand;
int F2[LIM][4], deg2[LIM][4], ok[4];
int fnd(int x) {
if(F[x]==x) return x;
return F[x]=fnd(F[x]);
}
int fnd2(int x, int y) {
if(F2[x][y]==x) return x;
return F2[x][y]=fnd2(F2[x][y], y);
}
void Init(int N) {
n=N; ans=n;
rep(i, n) {
F[i]=i;
ile[i]=1;
}
}
void usun(int x) {
kand.pb(x);
rep(i, q) if(kraw[i].st==x || kraw[i].nd==x) kand.pb(kraw[i].st^kraw[i].nd^x);
typ=2;
ans=0;
rep(j, 4) {
rep(i, n) F2[i][j]=i;
ok[j]=1;
rep(i, q) if(kraw[i].st!=kand[j] && kraw[i].nd!=kand[j]) {
if(fnd2(kraw[i].st, j)==fnd2(kraw[i].nd, j)) ok[j]=0;
F2[fnd2(kraw[i].st, j)][j]=fnd2(kraw[i].nd, j);
++deg2[kraw[i].st][j];
++deg2[kraw[i].nd][j];
if(deg2[kraw[i].st][j]==3 || deg2[kraw[i].nd][j]==3) ok[j]=0;
}
ans+=ok[j];
}
}
void upd(int a, int b) {
rep(i, 4) if(a!=kand[i] && b!=kand[i] && ok[i]) {
if(fnd2(a, i)==fnd2(b, i)) {
ok[i]=0;
--ans;
continue;
}
F2[fnd2(b, i)][i]=fnd2(a, i);
++deg2[a][i];
++deg2[b][i];
if(deg2[a][i]==3 || deg2[b][i]==3) {
ok[i]=0;
--ans;
continue;
}
}
}
void Link(int a, int b) {
if(ans==0) return;
kraw[q]={a, b};
++deg[a]; ++deg[b]; ++q;
if(typ==2) {
upd(a, b);
return;
}
if(deg[a]<deg[b]) swap(a, b);
if(deg[a]==3) {
usun(a);
return;
}
if(fnd(a)==fnd(b)) {
if(typ==1) ans=0;
else {
typ=1;
ans=ile[fnd(a)];
}
return;
}
ile[fnd(a)]+=ile[fnd(b)];
F[fnd(b)]=fnd(a);
}
int CountCritical() {
return ans;
}
