#include <bits/stdc++.h>
using namespace std;
int N,canticriti,asegu=-1;
vector<int> degree;
vector<vector<int>> graph;
vector<int> may3;
set<pair<int,int>> unidos;
void Init(int N_){
graph.resize(canticriti=N=N_);
degree.resize(N);
}
void Link(int A,int B){
if(canticriti==0){
return;
}
if(asegu!=-1){
if(A==asegu){
degree[A]++;
}else if(B==asegu){
degree[B]++;
}else{
degree[A]++;
degree[B]++;
if(degree[A]>2 || degree[B]>2){
canticriti=0;
}
}
}else{
unidos.insert({min(A,B),max(A,B)});
degree[A]++;
degree[B]++;
graph[A].push_back(B);
graph[B].push_back(A);
if(degree[A]>3 && degree[B]>3){
canticriti=0;
}else if(degree[A]>3){
asegu=A;
canticriti=1;
for(auto u:graph[A]){
degree[u]--;
}
}else if(degree[B]>3){
asegu=B;
canticriti=1;
for(auto u:graph[B]){
degree[u]--;
}
}else{
if(degree[A]==3){
may3.push_back(A);
}
if(degree[B]==3){
may3.push_back(B);
}
if(may3.size()>2){
//buscar al asegu
sort(may3.begin(),may3.end());
for(int i=0;i<may3.size();i++){
int con=0;
for(auto u:graph[may3[i]]){
if(binary_search(may3.begin(),may3.end(),u)){
con++;
}
}
if(con==may3.size()-1){
asegu=i;
break;
}
}
if(asegu==-1){
canticriti=0;
}
canticriti=1;
for(auto u:graph[asegu]){
degree[u]--;
}
}else if(may3.size()==2){
canticriti=2;
}else if(may3.size()==1){
canticriti=1+degree[may3[0]];
}
}
}
}
int CountCritical(){return canticriti;}
