// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
struct dsu{
int par[maxn];
void init(int n){
fill(par, par + n, -1);
}
int fnd(int u){
return par[u] < 0 ? u : par[u] = fnd(par[u]);
}
bool mrg(int a, int b){
if( (a = fnd(a)) == (b = fnd(b)) )
return 0;
if(par[a] > par[b])
swap(a, b);
par[a]+= par[b];
par[b] = a;
return 1;
}
};
struct solver{
bool ok;
int d[maxn];
dsu ds;
void init(int n){
ok = 1;
ds.init(n);
fill(d, d + n, 0);
}
void add(int a, int b){
if((++d[a]) > 2 || (++d[b]) > 2)
ok = 0;
if(!ds.mrg(a, b))
ok = 0;
}
};
solver sol[4];
dsu ds;
vector<pii> ed;
vector<int> imps;
vector<int> v[maxn];
int n;
int CYC;
bool bad;
void Init(int n){
::n = n;
for(int i = 0; i < n; i++)
v[i].clear();
imps.clear();
ed.clear();
for(int i = 0; i < 4; i++)
sol[i].init(n);
ds.init(n);
CYC = -1;
bad = 0;
}
void Link(int a, int b){
ed.PB({a, b});
v[a].PB(b), v[b].PB(a);
if(sz(v[a]) < sz(v[b]))
swap(a, b);
if(imps.empty() == 0){
for(int i = 0; i < 4; i++){
if(a != imps[i] && b != imps[i])
sol[i].add(a, b);
}
}
if(imps.empty() && sz(v[a]) > 2){
assert(sz(v[a]) == 3);
imps = v[a];
imps.PB(a);
for(pii p : ed){
for(int i = 0; i < 4; i++){
if(p.F != imps[i] && p.S != imps[i])
sol[i].add(p.F, p.S);
}
}
}
if(!ds.mrg(a, b)){
if(CYC != -1)
bad = 1;
CYC = -ds.par[ ds.fnd(a) ];
}
}
int CountCritical(){
int ans = 0;
if(imps.empty()){
if(bad == 0)
ans = CYC == -1 ? n : CYC;
}
else{
for(int i = 0; i < 4; i++)
ans+= sol[i].ok;
}
return ans;
}
