#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct union_find{
int size, num_components;
vector<int> sz, dad;
union_find(){}
union_find(int n){
size = n; num_components = n;
sz.resize(n);
dad.resize(n);
for (int i = 0; i < n; i++){
sz[i] = 1;
dad[i] = i;
}
}
int find(int x){
if (dad[x] == x) return x;
return dad[x] = find(dad[x]);
}
bool unite(int x, int y){ // returns true if already connected
x = find(x);
y = find(y);
if (x == y) return true;
if (sz[x] < sz[y]){
dad[x] = y;
sz[y] += sz[x];
} else {
dad[y] = x;
sz[x] += sz[y];
}
num_components--;
return false;
}
};
union_find uf(1);
vector<int> deg;
int mx_deg = 0;
int n;
vector<vector<int>> conns;
bool has_cyc = false;
set<int> pos{};
int ans;
map<int, pair<pair<bool, union_find>, pair<vector<int>, int>>> mp; // pos -> [has_cyc, uf], [degs, mx_deg]
void Init(int N){
n = N;
ans = n;
uf = union_find(n);
deg.resize(n);
conns.resize(n);
for (int i = 0; i < n; i++){
pos.insert(i);
}
}
void Link(int a, int b){
deg[a]++;
mx_deg = max(mx_deg, deg[a]);
deg[b]++;
mx_deg = max(mx_deg, deg[b]);
conns[a].push_back(b);
conns[b].push_back(a);
if (mx_deg <= 1){
uf.unite(a, b);
} if (mx_deg == 2){
if (uf.unite(a, b)){
if (has_cyc){
ans = 0;
pos = set<int>();
return;
} else {
int fnd = uf.find(a);
pos = {};
for (int i = 0; i < n; i++){
if (uf.find(i) == fnd){
pos.insert(i);
}
}
ans = pos.size();
has_cyc = true;
}
}
} else if (mx_deg == 3){
if (deg[a] == 3){
set<int> pos2{};
if (pos.count(a)){
pos2.insert(a);
}
for (int i : conns[a]){
if (pos.count(i)){
pos2.insert(i);
}
}
pos = pos2;
}
if (deg[b] == 3){
set<int> pos2{};
if (pos.count(b)){
pos2.insert(b);
}
for (int i : conns[b]){
if (pos.count(i)){
pos2.insert(i);
}
}
pos = pos2;
}
uf.unite(a, b);
} else {
if (deg[a] == 3){
set<int> pos2{};
if (pos.count(a)){
pos2.insert(a);
}
for (int i : conns[a]){
if (pos.count(i)){
pos2.insert(i);
}
}
pos = pos2;
} else if (deg[a] > 3){
if (pos.count(a)){
pos = {a};
} else {
pos = {};
}
}
if (deg[b] == 3){
set<int> pos2{};
if (pos.count(b)){
pos2.insert(b);
}
for (int i : conns[b]){
if (pos.count(i)){
pos2.insert(i);
}
}
pos = pos2;
} else if (deg[b] > 3){
if (pos.count(b)){
pos = {b};
} else {
pos = {};
}
}
uf.unite(a, b);
}
if (mx_deg >= 3){
ans = 0;
for (int x : pos){
if (!mp.count(x)){
mp[x] = {{false, union_find(n)}, {vector<int>(n), 0}};
for (int i = 0; i < n; i++){
if (i == x) continue;
for (int j : conns[i]){
if (j == x) continue;
if (j > i) continue;
mp[x].second.first[i]++;
mp[x].second.second = max(mp[x].second.second, mp[x].second.first[i]);
mp[x].second.first[j]++;
mp[x].second.second = max(mp[x].second.second, mp[x].second.first[j]);
if (mp[x].first.second.unite(i, j)){
mp[x].first.first = true;
}
}
}
} else {
if (a == x || b == x){
if (!mp[x].first.first && mp[x].second.second <= 2) ans++;
continue;
}
mp[x].second.first[a]++;
mp[x].second.second = max(mp[x].second.second, mp[x].second.first[a]);
mp[x].second.first[b]++;
mp[x].second.second = max(mp[x].second.second, mp[x].second.first[b]);
if (mp[x].first.second.unite(a, b)){
mp[x].first.first = true;
}
}
if (!mp[x].first.first && mp[x].second.second <= 2) ans++;
}
}
}
int CountCritical(){
return ans;
}
#ifdef LOCAL
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
Init(7);
cout << CountCritical() << "\n";
Link(0, 1);
cout << CountCritical() << "\n";
Link(1, 2);
cout << CountCritical() << "\n";
Link(2, 3);
cout << CountCritical() << "\n";
Link(3, 4);
cout << CountCritical() << "\n";
Link(4, 5);
cout << CountCritical() << "\n";
Link(5, 0);
cout << CountCritical() << "\n";
Link(0, 6);
cout << CountCritical() << "\n";
}
#endif
