#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> maxdegree(5, 0);
vector<int> candidates, edgeA, edgeB;
vector<vector<int>> degree(5), parent(5), height(5), compsize(5);
vector<bool> vis, valid(4, true);
vector<multiset<int>> cycles(5);
vector<vector<int>> adj;
vector<vector<vector<int>>> adjstates;
bool threestate = false;
int find(int node, int i){
// standard dsu find with the parent compression thing
if(parent[i][node] != node){
parent[i][node] = find(parent[i][node], i);
}
return parent[i][node];
}
void unite(int A, int B, int i){
// union by rank :3
int pa = find(A, i), pb = find(B, i);
int newcomp = compsize[i][pa] + compsize[i][pb];
if(height[i][pa] > height[i][pb]){
parent[i][pb] = pa;
height[i][pa] = max(height[i][pa], height[i][pb] + 1);
}
else{
parent[i][pa] = pb;
height[i][pb] = max(height[i][pb], height[i][pa] + 1);
}
compsize[i][parent[i][A]] = newcomp;
compsize[i][parent[i][B]] = newcomp;
}
void OmitCandidates(){
for(int i = 0; i < 4; i++){
for(int j = 0; j < edgeA.size(); j++){
if(edgeA[j] == candidates[i] || edgeB[j] == candidates[i]) continue;
adjstates[i][edgeA[j]].push_back(edgeB[j]);
adjstates[i][edgeB[j]].push_back(edgeA[j]);
degree[i+1][edgeA[j]]++;
degree[i+1][edgeB[j]]++;
maxdegree[i+1] = max(maxdegree[i+1], max(degree[i+1][edgeA[j]], degree[i+1][edgeB[j]]));
if(maxdegree[i+1] >= 3) valid[i] = false;
if(find(edgeA[j], i) == find(edgeB[j], i)) valid[i] = false;
else unite(edgeA[j], edgeB[j], i);
}
}
}
void Init(int N_) {
N = N_;
parent.assign(5, vector<int>(N)), height.assign(5, vector<int>(N)), adj.resize(N); adjstates.assign(4, vector<vector<int>>(N)), compsize.assign(5, vector<int>(N, 1));
degree.assign(5, vector<int>(N));
for(int i = 0; i < N; i++) for(int j = 0; j < 5; j++) parent[j][i] = i;
}
void Link(int A, int B) {
if(!threestate){
edgeA.push_back(A);
edgeB.push_back(B);
if(find(A, 0) == find(B, 0)) { // this is a cycle
cycles[0].insert(parent[0][A]);
cerr << A << " and " << B << " made a cycle!\n";
}
else unite(A, B, 0);
adj[A].push_back(B);
adj[B].push_back(A);
int degA = adj[A].size(), degB = adj[B].size();
maxdegree[0] = max(maxdegree[0], max(degA, degB));
if(maxdegree[0] == 3){
threestate = true;
if(degA == 3){
candidates.push_back(A);
for(int i : adj[A]) candidates.push_back(i);
}
else if(degB == 3){
candidates.push_back(B);
for(int i : adj[B]) candidates.push_back(i);
}
OmitCandidates();
}
}
else{
for(int i = 1; i < 5; i++){
if(A != candidates[i-1] && B != candidates[i-1]){
if(find(A, i) == find(B, i)) { // this is a cycle
valid[i-1] = false;
}
adjstates[i-1][A].push_back(B);
adjstates[i-1][B].push_back(A);
int degA = adjstates[i-1][A].size(), degB = adjstates[i-1][B].size();
maxdegree[i] = max(maxdegree[i], max(degA, degB));
if(maxdegree[i] == 3) valid[i-1] = false;
}
}
}
}
int CountCritical() {
int ret = 0;
if(!threestate){
if(maxdegree[0] <= 1) ret = N;
else if(cycles[0].size() >= 2) ret = 0;
else{
if(cycles[0].size() == 1) ret = compsize[0][*cycles[0].begin()];
else ret = N;
}
}
else{
for(bool i : valid) ret += i;
}
return ret;
}
