#include "bits/stdc++.h"
using namespace std;
#define ll int
#define MAXN 1000005
#define _ << " " <<
//definizioni globali
vector<array<ll, 2> > edges;
ll ris=-1, stato = 0;
ll n;
vector<ll> adj[MAXN];
struct grafo{
ll par[MAXN], size[MAXN], deg[MAXN];
ll can = -1, nc = 0, idx = -1;
//union find
ll find(ll a){
if(par[a] == a) return a;
return par[a]=find(par[a]);
}
bool same(ll a, ll b){
return find(a) == find(b);
}
void unite(ll a, ll b){
a = find(a);
b = find(b);
if(size[a] > size[b]) swap(a, b);
par[a] = b;
size[b] += size[a];
}
//archi
void link(ll a, ll b){
if(a == can || b == can) return;
//cout << a _ b _ idx << " ";
deg[a]++;
deg[b]++;
bool check = 0;
if(deg[a] == 2 && deg[b] == 2 && same(a, b)) check = 1; //creo un ciclo
if(deg[a] == 3 || deg[b] == 3) check = 1; //nodo con grado >= 3
if(!same(a, b)) unite(a, b);
if(check){
if(idx == -1 || !same(idx, a)){
nc++; idx = a;
}
}
if(idx != -1) idx = find(idx);
//cout << idx << endl;
}
//build
void init(ll n){
for(ll i=0; i<n; ++i){
par[i] = i;
size[i] = 1;
}
for(auto u : edges)
link(u[0], u[1]);
}
};
grafo G[5];
void Init(int N) {
n = N;
G[0].init(N);
}
void Link(int a, int b) {
if(stato == 0) edges.push_back({a, b});
adj[a].push_back(b);
adj[b].push_back(a);
grafo &g = G[0];
g.link(a, b);
for(ll i=0; i<n; ++i){
//cout << i _ g.find(i) << endl;
}
// aggiorno i 4 grafi alternativi
if(stato == 1) for(ll i=1; i<5; ++i) G[i].link(a, b);
//primo nodo con grado >= 3
if(stato == 0){
if(g.deg[a] == 3){
stato = 1;
G[1].can = a; G[2].can = adj[a][0]; G[3].can = adj[a][1]; G[4].can = adj[a][2]; }
else if(g.deg[b] == 3){
stato = 1;
G[1].can = b; G[2].can = adj[b][0]; G[3].can = adj[b][1]; G[4].can = adj[b][2]; }
// costruisco i 4 grafi alternativi
if(stato == 1) for(ll i=1; i<5; ++i) G[i].init(n);
}
}
int CountCritical() {
if(ris == 0)
return 0;
grafo &g = G[0];
//cout << endl << g.nc << " " << g.idx << endl;
if(g.nc == 0)
return n;
if(g.nc >= 2)
return ris = 0;
//g.nc == 1
if(stato == 0)
return g.size[g.idx];
//stato >= 1
ll cnt =0;
for(ll i= 1; i<5; ++i)
cnt += (G[i].nc == 0);
return ris = cnt;
}
