#include <iostream>
#include<bits/stdc++.h>
using namespace std;
std::vector<vector<int>> Connections;
vector<int> CritId;
vector<vector<int>> TreeCritId;
vector<pair<int,int>> Fixes;
void Init(int N) {
Connections=std::vector<vector<int>>(N);
CritId=vector<int>();
}
int getRoot(int A,vector<int>& Tree) {
if(Tree[A]==A) {
return A;
}
int pos=getRoot(Tree[A],Tree);
Tree[A]=pos;
return pos;
}
void join(int A,int B,vector<int>& Tree) {
Tree[getRoot(A,Tree)]=getRoot(B,Tree);
}
void pLink(int A,int B,int N) {
Connections[A].push_back(B);
if(Connections[A].size()<3) {
return;
}
if(Connections[A].size()==3 && CritId.size()==0) {
CritId.push_back(A);
for(int i=0; i<3; i++) {
CritId.push_back(Connections[A][i]);
}
vector<int>Tree;
for(int i=0; i<N; i++) {
Tree.push_back(i);
}
for(int i=0; i<4; i++) {
TreeCritId.push_back(Tree);
}
for(int j=0; j<Fixes.size(); j++) {
int tA=Fixes[j].first;
int tB=Fixes[j].second;
for(int i=0; i<4; i++) {
if(CritId[i]!=-1 && CritId[i]!=tA && CritId[i]!=tB) {
if(getRoot(tA,TreeCritId[i])==getRoot(tB,TreeCritId[i])) {
CritId[i]=-1;
}
else {
join(tA,tB,TreeCritId[i]);
}
}
}
}
return;
}
if(Connections[A].size()==3) {
Connections[A].push_back(B);
for(int i=0; i<4; i++) {
bool Valid=false;
if(CritId[i]==A) {
Valid=true;
}
for(int j=0; j<3; j++) {
if(CritId[i]==Connections[A][j]) {
Valid=true;
}
}
if(!Valid) {
CritId[i]=-1;
}
}
return;
}
for(int i=0;i<4;i++){
if(CritId[i]!=A) {
CritId[i]=-1;
}
}
return;
}
void Link(int A, int B) {
pLink(A,B,Connections.size());
pLink(B,A,Connections.size());
if(CritId.size()==0){
Fixes.push_back({A,B});
return;
}
for(int i=0; i<4; i++) {
if(CritId[i]!=-1 && CritId[i]!=A && CritId[i]!=B) {
if(getRoot(A,TreeCritId[i])==getRoot(B,TreeCritId[i])){
CritId[i]=-1;
}
else {
join(A,B,TreeCritId[i]);
}
}
}
}
int CountCritical() {
if(CritId.size()==0){
return Connections.size();
}
int v=0;
for(int i=0;i<4;i++){
if(CritId[i]!=-1){
v++;
}
}
return v;
}
