//#include "crocodile.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 1000000000
#define mod 998244353
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001
using namespace std;
vec<int> poc;
int pocet4 = 0;
vec<vec<int>> g;
int faza2 = 0;
vec<int> o;
vec<vec<int>> mp;
int n;
int otec(int x) {
if (o[x] < 0) return x;
o[x] = otec(o[x]);
return o[x];
}
set<int> r;
void Init(int n2) {
n = n2;
g.resize(n);
mp.resize(n);
For(i, n) mp[i].push_back(i);
o.resize(n, -1);
poc.resize(n, 0);
For(i, n) r.insert(i);
return;
}
void Link(int a, int b) {
poc[a]++; poc[b]++;
g[a].push_back(b);
g[b].push_back(a);
if (poc[a] == 4) {
pocet4++;
r.clear();
if(pocet4 == 1) r.insert(a);
}
if (poc[a] == 3) {
faza2 = 1;
set<int> r2;
if (r.find(a) != r.end()) {
r2.insert(a);
}
for (auto i : g[a]) {
if (r.find(i) != r.end()) {
r2.insert(i);
}
}
r = r2; r2.clear();
}
if (poc[b] == 4) {
pocet4++;
r.clear();
if(pocet4 == 1) r.insert(b);
}
if (poc[b] == 3) {
faza2 = 1;
set<int> r2;
if (r.find(b) != r.end()) {
r2.insert(b);
}
for (auto i : g[b]) {
if (r.find(i) != r.end()) {
r2.insert(i);
}
}
r = r2; r2.clear();
}
if (faza2 != 0) return;
if (otec(a) != otec(b)) {
a = otec(a);
b = otec(b);
if (mp[a].size() < mp[b].size()) swap(a, b);
o[otec(b)] = otec(a);
for (auto i : mp[b]) mp[a].push_back(i);
mp[b].clear();
}
else {
a = otec(a);
b = otec(b);
set<int> r2;
for (auto i : mp[a]) {
if (r.find(i) != r.end()) {
r2.insert(i);
}
}
r = r2; r2.clear();
}
return;
}
bool dfs(int x, int pr, int s, vec<bool>&bol) {
if (bol[x]) return 0;
bol[x] = 1;
int k = 0;
bool je = 1;
for (auto i : g[x]) {
if (i == s) continue;
k++;
if (i == pr) continue;
je &= dfs(i, x, s, bol);
}
if (k > 2) je = 0;
return je;
}
int check(int x) {
bool je = 1;
vec<bool> bol(n, false);
for (auto i : g[x]) {
if (bol[i]) continue;
je &= dfs(i, x, x, bol);
}
return je;
}
int CountCritical() {
if (faza2 == 0) {
return r.size();
}
if (faza2 == 1) {
int vys = 0;
for (auto i : r) {
vys += check(i);
}
return vys;
}
return 0;
}
/*
signed main() {
//ll t; cin >> t;
ll t = 1;
For(w, t){
int n, q; cin >> n >> q;
Init(n);
For(i, q) {
int x; cin >> x;
if (x == -1) {
cout << CountCritical() << '\n';
}
else {
int y; cin >> y;
Link(x, y);
}
}
}
return 0;
}*/
