#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n , comp[N], mx , adj[N] , ans = 0 , cycles = 0 , vis[N] , vi = 0 , comp2[4][N] , con1[4][N] , con2[4][N] , qu[N] , in[N] , idx = 0 , u , vv;
vector< int > g[N];
vector< pair<int,bool> > v;
vector< pair<int,int> > v2;
void Init(int N_) {
n = N_;
ans = n ;
for(int i=0;i<n;i++)
comp[i] = i;
mx = 0 ;
cycles = 0 ;
}
void DFS(int node,int prnt,int last){
while(true){
ans++;
if(node == last) return;
for(int i=0;i<(int)g[node].size();i++){
if(g[node][i] != prnt){
prnt = node;
node = g[node][i];
break;
}
}
}
}
void make(int u){
v.push_back(make_pair(u,true));
for(int i=0;i<(int)g[u].size();i++){
v.push_back(make_pair(g[u][i],true));
}
ans = 0 ;
int st = 0 , en = 1 , num = 0 , node = 0;
for(int i=0;i<(int)v.size();i++){
vi++;
for(int j=0;j<n;j++){
if(j == v[i].first || vis[j] == vi) continue;
con1[i][j] = con2[i][j] = -1;
st = 0 , en = 1 , num = 0 , node = j;
qu[0] = j;
vis[j] = vi;
while(st < en){
node = qu[st++];
comp2[i][node] = j;
num = 0 ;
for(int k=0;k<(int)g[node].size();k++){
num += (g[node][k] != v[i].first);
if(vis[g[node][k]] == vi || g[node][k] == v[i].first) continue;
qu[en++] = g[node][k];
vis[g[node][k]] = vi;
}
if(num < 2){
if(con1[i][j] == -1) con1[i][j] = node; else con2[i][j] = node;
}
}
if(con1[i][j] == -1){
v[i].second = false;
break;
}
if(con2[i][j] == -1) con2[i][j] = con1[i][j];
}
ans += v[i].second;
}
}
void Link(int a, int b) {
if(ans == 0) return;
if(mx < 3){
u = a;
idx = 0 ;
while(u != comp[u]){
in[idx++] = u;
u = comp[u];
}
while(idx > 0){
idx--;
comp[in[idx]] = u;
}
vv = b;
idx = 0 ;
while(vv != comp[vv]){
in[idx++] = vv;
vv = comp[vv];
}
while(idx > 0){
idx--;
comp[in[idx]] = vv;
}
adj[a]++;
adj[b]++;
g[a].push_back(b);
g[b].push_back(a);
if(adj[a] == 3){
mx = 3;
make(a);
return ;
}
if(adj[b] == 3){
mx = 3;
make(b);
return;
}
if(u == vv){
if(cycles > 0){
ans = 0;
return ;
}
cycles++;
ans = 0 ;
DFS(a,b,b);
}
else{
comp[u] = vv;
}
return ;
}
for(int i=0;i<(int)v.size();i++){
if(v[i].second == false) continue;
if(a == v[i].first || b == v[i].first){
adj[v[i].first]++;
if(adj[v[i].first] > 3 && v.size() > 1){
int cur = v[i].first;
ans = 1;
v.clear();
v.push_back(make_pair(cur,1));
break;
}
continue;
}
u = comp2[i][a];
idx = 0;
while(u != comp2[i][u]){
in[idx++] = u;
u = comp2[i][u];
}
while(idx > 0){
idx--;
comp2[i][in[idx]] = u;
}
vv = comp2[i][b];
idx = 0;
while(vv != comp2[i][vv]){
in[idx++] = vv;
vv = comp2[i][vv];
}
while(idx > 0){
idx--;
comp2[i][in[idx]] = vv;
}
if(u == vv){
v[i].second = false;
ans--;
continue;
}
if(a != con1[i][u] && a != con2[i][u]){
v[i].second = false;
ans--;
continue;
}
if(b != con1[i][vv] && b != con2[i][vv]){
v[i].second = false;
ans--;
continue;
}
comp2[i][u] = vv;
if(a == con1[i][u] && b == con1[i][vv]){
con1[i][vv] = con2[i][u];
}
else if(a == con2[i][u] && b == con1[i][vv]){
con1[i][vv] = con1[i][u];
}
else if(a == con1[i][u] && b == con2[i][vv]){
con2[i][vv] = con2[i][u];
}
else if(a == con2[i][u] && b == con2[i][vv]){
con2[i][vv] = con1[i][u];
}
}
}
int CountCritical() {
return ans;
}
