#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template <typename Key, typename Value>
using hash_map = unordered_map<Key, Value, custom_hash>;
// greatest best, U F D S
struct DSU {
int n;
vector<int> parent, size;
vector<bool> conn;
DSU(int n) : n(n) {
conn.assign(n, false);
size.assign(n, 1);
parent.resize(n);
for (int i = 0; i < n; i++)
parent[i] = i;
}
bool check(int u, int v) {
u = find(u), v = find(v);
return u == v;
}
int find(int u) {
if (parent[u] == u)
return u;
return parent[u] = find(parent[u]);
}
bool unite(int u, int v) {
u = find(u), v = find(v);
if (u == v)
return true;
parent[v] = u;
size[u] += size[v];
return false;
}
};
struct state {
int mx;
bool flag;
DSU *dsu;
vector<int> adj;
state(int mx = 0, bool flag = false) : mx(mx), flag(flag) {
dsu = new DSU(n);
adj.resize(n);
}
};
int ans, mx;
vector<vector<int>> adj;
bool flag, stop;
set<int> can;
hash_map<int, state> rem;
DSU *dsu;
void Init(int N_) {
n = ans = N_;
mx = flag = stop = 0;
adj.resize(n);
dsu = new DSU(n);
for (int i = 0; i < n; i++) {
can.insert(i);
}
}
// N->L->4->3->2->1->0
void Link(int u, int v) {
if (stop) {
return;
}
adj[u].push_back(v);
adj[v].push_back(u);
mx = max(mx, (int)adj[u].size());
mx = max(mx, (int)adj[v].size());
// trivial (no components are more than pairs)
if (mx == 1) {
dsu->unite(u, v);
}
// check for L
else if (mx == 2) {
// already in the same component
if (dsu->unite(u, v)) {
// there already exists a loop
if (flag) {
can.clear();
ans = can.size();
}
// because mx == 2, this is a loop
else {
can.clear();
for (int i = 0; i < n; i++) {
if (dsu->check(u, i)) {
can.insert(i);
}
}
ans = can.size();
flag = 1;
}
}
// only lines
else {
// nothing
;;
}
}
// there is a lot of casework here
else if (mx == 3) {
// if either of the two are new candidates
// check if they are in the same component as can
if (adj[u].size() == 3) {
set<int> temp;
if (can.count(u)) {
temp.insert(u);
}
for (auto &w : adj[u]) {
if (can.count(w)) {
temp.insert(w);
}
}
can = temp;
}
if (adj[v].size() == 3) {
set<int> temp;
if (can.count(v)) {
temp.insert(v);
}
for (auto &w : adj[v]) {
if (can.count(w)) {
temp.insert(w);
}
}
can = temp;
}
dsu->unite(u, v);
}
// there is only one candidate
else if (mx >= 4) {
if (adj[u].size() == 3) {
set<int> temp;
if (can.count(u)) {
temp.insert(u);
}
for (auto &w : adj[u]) {
if (can.count(w)) {
temp.insert(w);
}
}
can = temp;
}
else if (adj[u].size() > 3) {
can.clear();
if (can.count(u)) {
can.insert(u);
}
}
if (adj[v].size() == 3) {
set<int> temp;
if (can.count(v)) {
temp.insert(v);
}
for (auto &w : adj[v]) {
if (can.count(w)) {
temp.insert(w);
}
}
can = temp;
}
else if (adj[v].size() > 3) {
can.clear();
if (can.count(v)) {
can.insert(v);
}
}
dsu->unite(u, v);
}
// simulate removing vertices
if (mx >= 3) {
ans = 0;
for (auto &w : can) {
if (rem.count(w)) {
// no need to process unite
if (u == w || v == w) {
if (!rem[w].flag && rem[w].mx <= 2)
ans++;
}
else {
rem[w].adj[u]++;
rem[w].adj[v]++;
rem[w].mx = max(rem[w].mx, max(rem[w].adj[u], rem[w].adj[v]));
if (rem[w].dsu->unite(u, v)) {
rem[w].flag = true;
}
// check
if (!rem[w].flag && rem[w].mx <= 2)
ans++;
}
}
// init
else {
rem[w] = state();
for (int i = 0; i < n; i++) {
if (i == w)
continue;
for (auto &j : adj[i]) {
if (j == w)
continue;
if (j > i)
continue;
rem[w].adj[i]++;
rem[w].adj[j]++;
rem[w].mx = max(rem[w].mx, max(rem[w].adj[i], rem[w].adj[j]));
if (rem[w].dsu->unite(i, j)) {
rem[w].flag = true;
}
}
}
// check
if (!rem[w].flag && rem[w].mx <= 2)
ans++;
}
// cerr << rem[w].flag << " " << rem[w].mx << endl;
}
}
if (ans == 0) {
stop = true;
}
}
int CountCritical() {
return ans;
}
// int main() {
// int n, l; cin >> n >> l;
// Init(n);
// for (int i = 0; i < l; i++) {
// int a, b; cin >> a;
// if (a == -1) {
// cout << CountCritical() << endl;
// } else {
// cin >> b;
// Link(a, b);
// }
// }
// }
