#include <bits/stdc++.h>
using namespace std;
int N, cycles, lastcycle;
vector<int> maxdegree(5, 0);
vector<int> candidates, edgeA, edgeB, compsize;
vector<bool> valid(4, true);
vector<vector<int>> parent(5), height(5);
vector<vector<int>> adj, prefix;
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 newcomp = 0;
int pa = find(A, i), pb = find(B, i);
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);
}
if(i == 0){
newcomp = compsize[pa] + compsize[pb];
compsize[parent[i][A]] = newcomp;
compsize[parent[i][B]] = newcomp;
}
}
void OmitCandidates(){
for(int i = 0; i < 4; i++){
vector<vector<int>> nadj(N);
for(int j = 0; j < edgeA.size(); j++){
if(edgeA[j] == candidates[i] || edgeB[j] == candidates[i]) continue;
nadj[edgeA[j]].push_back(edgeB[j]);
nadj[edgeB[j]].push_back(edgeA[j]);
maxdegree[i+1] = max(maxdegree[i+1], (int)max(nadj[edgeA[j]].size(), nadj[edgeB[j]].size()));
if(maxdegree[i+1] >= 3) valid[i] = false;
if(find(edgeA[j], i+1) == find(edgeB[j], i+1)) valid[i] = false;
else unite(edgeA[j], edgeB[j], i+1);
}
for(int j : adj[candidates[i]]) prefix[i][j]++;
}
}
void Init(int N_) {
N = N_;
parent.assign(5, vector<int>(N)), height.assign(5, vector<int>(N)), adj.resize(N); prefix.assign(4, vector<int>(N, 0)), compsize.assign(N, 1);
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
lastcycle = compsize[parent[0][A]];
cycles++;
}
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{
adj[A].push_back(B);
adj[B].push_back(A);
for(int i = 1; i < 5; i++){
if(!valid[i-1]) continue;
if(candidates[i-1] == A){
prefix[i-1][A]++;
continue;
}
if(candidates[i-1] == B){
prefix[i-1][B]++;
continue;
}
int degA = adj[A].size() - prefix[i-1][A], degB = adj[B].size() - prefix[i-1][B];
maxdegree[i] = max(maxdegree[i], max(degA, degB));
if(maxdegree[i] >= 3) valid[i-1] = false;
else {
if(find(A, i) == find(B, i)) { // this is a cycle
valid[i-1] = false;
}
else unite(A, B, i);
}
}
}
}
int CountCritical() {
int ret = 0;
if(!threestate){
if(maxdegree[0] <= 1) ret = N;
else if(cycles>= 2) ret = 0;
else{
if(cycles == 1) ret = lastcycle;
else ret = N;
}
}
else{
for(bool i : valid) ret += i;
}
return ret;
}
