#include<bits/stdc++.h>
using namespace std;
const int lim = 1e6+5;
struct UF{
int N;
int pai[lim], qtd_vert[lim], deg[lim];
int circle_sz;
UF(){}
UF(int _N){
N = _N;
circle_sz = 0;
for(int i = 1; i <= N; i++){
pai[i] = i;
qtd_vert[i] = 1;
}
};
int CRings(){
if(circle_sz == 0) return N;
if(circle_sz == -1) return 0;
return circle_sz;
}
void newCircle(int no){
if(circle_sz == 0){
circle_sz = qtd_vert[no];
}
else{
circle_sz = -1;
}
}
int find(int no){
if(pai[no] == no) return no;
return pai[no] = find(pai[no]);
}
void merge(int a, int b){
deg[a]++; deg[b]++;
if(deg[a] > 2 || deg[b] > 2) circle_sz = -1;
a = find(a); b = find(b);
if(qtd_vert[a] < qtd_vert[b]) swap(a, b);// a será novo representante
pai[b] = a;
if(a != b) qtd_vert[a] += qtd_vert[b];
else newCircle(a);
}
};
UF princ, rt, v1, v2, v3;
int n, ROOT, V1, V2, V3;
vector<pair<int, int>> linked;
void Init(int N_) {
n = N_;
princ = UF(n);
}
bool deg3 = false;
vector<int> adj[lim];
void buildSubUF(int root){
deg3 = true;
ROOT = root;
V1 = adj[root][0];
V2 = adj[root][1];
V3 = adj[root][2];
rt = UF(n);
v1 = UF(n);
v2 = UF(n);
v3 = UF(n);
for(auto no : linked){
int A = no.first, B = no.second;
if(A != ROOT && B != ROOT) rt.merge(A, B);
if(A != V1 && B != V1) v1.merge(A, B);
if(A != V2 && B != V2) v2.merge(A, B);
if(A != V3 && B != V3) v3.merge(A, B);
}
}
void Link(int A, int B) {
A++; B++;
adj[A].push_back(B);
adj[B].push_back(A);
linked.emplace_back(A, B);
if(!deg3){ //link normal nos main UF
princ.merge(A, B);
if(princ.deg[A] > 2){
buildSubUF(A);
return;
}
if(princ.deg[B] > 2){
buildSubUF(B);
return;
}
}
else{
//link nos 4 sub UF;
if(A != ROOT && B != ROOT) rt.merge(A, B);
if(A != V1 && B != V1) v1.merge(A, B);
if(A != V2 && B != V2) v2.merge(A, B);
if(A != V3 && B != V3) v3.merge(A, B);
}
}
int CountCritical() {
if(deg3) return rt.CRings()+v1.CRings()+v2.CRings()+v3.CRings();
else return princ.CRings();
}
