#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int n, m, mx;
vector<int> way[maxn];
pair<int,int> e[maxn];
int cysz, ban[5], bad[5], cyc[5];
int head[5][maxn], sz[5][maxn], deg[5][maxn];
void Init(int _n) {
n = _n;
for(int k=0;k<=4;k++) {
for(int i=1;i<=n;i++) {
head[k][i] = i;
sz[k][i] = 1;
}
}
}
int CountCritical() {
if(mx<=2) {
if(cyc[0]==0) return n;
if(cyc[0]==1) return cysz;
return 0;
}
else {
int res = 0;
for(int i=1;i<=4;i++) res += !bad[i];
return res;
}
}
int findhead(int k, int x) {
if(head[k][x]==x) return x;
return head[k][x] = findhead(k, head[k][x]);
}
void edge(int k, int u, int v) {
if(ban[k]==u || ban[k]==v) return ;
++deg[k][u]; ++deg[k][v];
if(deg[k][u]==3) bad[k] = 1;
if(deg[k][v]==3) bad[k] = 1;
int x = findhead(k,u), y = findhead(k,v);
if(x==y) {
bad[k] = 1;
cyc[k]++;
if(k==0) cysz = sz[k][x];
}
else {
sz[k][y] += sz[k][x];
head[k][x] = y;
}
}
void build(int x) {
ban[1] = x;
for(int i=0;i<3;i++) ban[i+2] = way[x][i];
for(int i=1;i<=m;i++) {
for(int k=1;k<=4;k++) edge(k,e[i].first,e[i].second);
}
}
void Link(int x, int y) {
x++; y++;
way[x].push_back(y); way[y].push_back(x);
e[++m] = {x,y};
edge(0,x,y);
if(mx<=2) {
if(way[x].size()==3) build(x);
else if(way[y].size()==3) build(y);
}
else {
for(int k=1;k<=4;k++) edge(k,x,y);
}
mx = max(mx, (int)way[x].size());
mx = max(mx, (int)way[y].size());
}
