#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
#define repi(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
struct UnionFind{
int N;
vector<int> par, siz, dig;
int exc;
bool ok = true;
void init(int n, int _exc){
N = n;
par = vector<int>(N, -1);
siz = vector<int>(N, 1);
exc = _exc;
dig = vector<int>(N, 0);
}
int root(int a){
if(par[a] == -1) return a;
return par[a] = root(par[a]);
}
int unite(int a, int b){
if(a == exc || b == exc) return 1;
dig[a]++; dig[b]++;
ok &= (dig[a] <= 2 && dig[b] <= 2);
int ra = root(a), rb = root(b);
if(ra == rb){
ok = false;
return 0;
}
if(siz[ra] > siz[rb]){
par[rb] = ra;
siz[ra] += siz[rb];
}
else{
par[ra] = rb;
siz[rb] += siz[ra];
}
return 1;
}
bool isSame(int a, int b){
return root(a) == root(b);
}
int size(int a){
return siz[root(a)];
}
};
int N;
int phase = 2, circle = 0, C = 0;
vector<pair<int,int>> note;
vector<int> e[1000000];
UnionFind base, spec[4], spec4;
void Init(int N_) {
N = N_;
base.init(N, -1);
}
void Link(int A, int B) {
note.pb({A,B});
e[A].pb(B);
e[B].pb(A);
if(phase == 2){
if(e[A].size() == 3){
phase = 3;
spec[0].init(N, A);
rep(i, 3) spec[i+1].init(N, e[A][i]);
rep(i, 4) for(auto [a,b]:note){
spec[i].unite(a, b);
}
return;
}
if(e[B].size() == 3){
phase = 3;
spec[0].init(N, B);
rep(i, 3) spec[i+1].init(N, e[B][i]);
rep(i, 4) for(auto [a,b]:note){
spec[i].unite(a, b);
}
return;
}
if(base.unite(A, B) == 0){
circle++;
if(circle == 1){
C = base.size(A);
return;
}
}
}
else if(phase == 3){
if(e[A].size() == 4){
phase = 4;
spec4.init(N, A);
for(auto [a,b]:note){
spec4.unite(a, b);
}
return;
}
if(e[B].size() == 4){
phase = 4;
spec4.init(N, B);
for(auto [a,b]:note){
spec4.unite(a, b);
}
return;
}
rep(i, 4) spec[i].unite(A, B);
}
else{
spec4.unite(A, B);
}
}
int CountCritical() {
if(phase == 2){
if(circle == 0) return N;
else if(circle == 1) return C;
else return 0;
}
else if(phase == 3){
return (int)spec[0].ok + (int)spec[1].ok + (int)spec[2].ok + (int)spec[3].ok;
}
else{
return (int)spec4.ok;
}
return -1;
}
