#include <bits/stdc++.h>
using namespace std;
#define F(i, n) for (int i = 0; i < (n); i++)
#define F_reverse(i, n) for (int i = (n - 1); i >= 0; i--)
#define N 1000000
/*
ideas
deleting a node should result in graph where max degree is 2, and no cycles
so if there are nodes with degree >= 3, the node needs to be connected to all
other instances
only 1 component can have degree 3/4
case max node with upto degree >= 4:
only one with deg >= 4 can occur (otherwise no critical), and it is the only one that can be critical
it can be connected to O(n) nodes with degree 3
case node with upto degree == 3:
at most 4 3degs can occur (otherwise no critical), (3deg connected to 3 3degs)
only possible crits are them and nodes connected to them (around 16 max?)
based from hints
1. state machine that based on max deg node from 2 -> 3 -> 4+
1. if there are <= 4 3degs, naively create multiple graphs without a specific
node, and ensure they have no cycle
2. the 5th 3deg and above: skip creating sans that node-graphs their neighbors
3. the moment the 1st 4deg is created: replace graphs with sans that node graph
case node with upto degree == 2 only:
ensure upto one cycle only
impl: everthing in the connected component is crit
can store count of connected components with cycles
*/
struct dsu_clean {
int p[N]; // parent node
int sz[N]; // size of component
void init(int n) {
F(i, n) {
p[i] = i;
sz[i] = 1;
}
}
int find(int x) {
if (p[x] == x) {
return x;
}
int ret = find(p[x]);
p[x] = ret;
return ret;
}
bool united(int a, int b) {
int x = find(a);
int y = find(b);
return x == y;
}
void unite(int a, int b) {
int x = find(a);
int y = find(b);
if (x != y) {
if (sz[x] < sz[y]) {
swap(x, y);
}
p[y] = x;
sz[x] += sz[y];
}
}
};
int n;
vector<pair<int, int>> link_list; // not to be confused with a linked list
//struct graph_sans_specific_node;
struct graph_sans_specific_node {
dsu_clean dsu;
bool has_cycle_flag = false;
int excl_node;
graph_sans_specific_node(int excl_node) {
dsu.init(n);
this->excl_node = excl_node;
for(auto [u, v] : link_list) {
process_input(u, v);
}
};
void process_input(int u, int v) {
//cout << excl_node << " recv " << u << " " << v << endl;
if(u != excl_node && v != excl_node) {
if(dsu.united(u, v)) {
////cout << "has cycle" << endl;
this->has_cycle_flag = true;
} else {
dsu.unite(u, v);
}
}
}
};
unordered_map<int, graph_sans_specific_node> graphs_without_specific_nodes;
struct dsu_main {
int p[N]; // parent node
int sz[N]; // size of component
// misc params
int num_4plus_deg[N];
int v_4plus_deg[N]; // assumes one only
bool has_cycle[N];
// limit to 4
vector<unordered_set<int>> v_3_deg;
void init(int n) {
F(i, n) {
p[i] = i;
sz[i] = 1;
}
v_3_deg.resize(n);
}
int find(int x) {
if (p[x] == x) {
return x;
}
int ret = find(p[x]);
p[x] = ret;
return ret;
}
void unite(int a, int b) {
int x = find(a);
int y = find(b);
if (x != y) {
if (sz[x] < sz[y]) {
swap(x, y);
}
p[y] = x;
sz[x] += sz[y];
num_4plus_deg[x] += num_4plus_deg[y];
if (num_4plus_deg[x] == 0 && num_4plus_deg[y] > 0) { // move to x
v_4plus_deg[x] = v_4plus_deg[y];
}
for (int v : v_3_deg[y]) {
if (v_3_deg[x].size() > 4) {
break;
}
v_3_deg[x].insert(v);
}
has_cycle[x] |= has_cycle[y];
}
}
} dsu;
struct vertex_info {
bool in_cyle;
vector<int> edge_list;
unordered_set<int> _3deg_neighbors;
size_t count_3deg_neighbors() { return _3deg_neighbors.size(); }
bool is_3deg() { return edge_list.size() == 3; }
};
vector<vertex_info> info(N);
unordered_set<int> get_3deg_and_neighbors(int u) {
unordered_set<int> nodes, vis;
int p = dsu.find(u);
for (auto v : dsu.v_3_deg[p]) {
//cout << v << " has 3 edges" << endl;
for (auto u : info[v].edge_list) {
// if(vis.contains(u)) {
// continue;
// }
// vis.insert(u);
nodes.insert(u);
}
nodes.insert(v);
}
return nodes;
}
void Init(int N_) {
dsu.init(N_);
n = N_;
}
size_t _3deg_node_cnt = 0, _4plusdeg_node_cnt = 0;
unordered_set<int> components_with_3deg, components_with_4plusdeg, components_with_cycle;
void Link(int A, int B) {
link_list.emplace_back(A, B);
for(auto& [_, g] : graphs_without_specific_nodes) { // note & is needed
g.process_input(A, B);
}
int u = dsu.find(A), v = dsu.find(B);
components_with_3deg.erase(u);
components_with_4plusdeg.erase(u);
components_with_3deg.erase(v);
components_with_4plusdeg.erase(v);
components_with_cycle.erase(u);
components_with_cycle.erase(v);
if(u == v) {
// cycle detected
dsu.has_cycle[u] = true;
}
// //cout << A << ' ' << B << endl;
info[A].edge_list.push_back(B);
info[B].edge_list.push_back(A);
auto handle_changes = [&](int u, int dsu_rep) {
int deg = info[u].edge_list.size();
if (deg == 3) {
for (int v : info[u].edge_list) {
info[v]._3deg_neighbors.insert(u);
}
dsu.v_3_deg[dsu_rep].insert(u);
_3deg_node_cnt++;
if(_4plusdeg_node_cnt == 0 && _3deg_node_cnt <= 4) {
auto community = get_3deg_and_neighbors(u);
for(int v : community) {
if(graphs_without_specific_nodes.find(v) == graphs_without_specific_nodes.end()) {
graphs_without_specific_nodes.emplace(v, graph_sans_specific_node(v));
}
}
}
} else if (deg == 4) {
for (int v : info[u].edge_list) {
info[v]._3deg_neighbors.erase(u);
}
dsu.v_3_deg[dsu_rep].erase(u);
_3deg_node_cnt--;
_4plusdeg_node_cnt++;
if(_4plusdeg_node_cnt == 1) {
graphs_without_specific_nodes.clear();
graphs_without_specific_nodes.emplace(u, graph_sans_specific_node(u));
}
}
};
handle_changes(A, u);
handle_changes(B, v);
dsu.unite(A, B);
int p = dsu.find(A);
if(dsu.num_4plus_deg[p] > 0) {
components_with_4plusdeg.insert(p);
}
if(dsu.v_3_deg[p].size() > 0) {
components_with_3deg.insert(p);
}
if(dsu.has_cycle[p]) {
components_with_cycle.insert(p);
}
//cout << "components with 3deg: " << components_with_3deg.size() << endl;
//cout << "components with 4+deg: " << components_with_4plusdeg.size() << endl;
}
int CountCritical() {
if(components_with_4plusdeg.size() > 0) {
//cout << "case 4+\n";
if(components_with_4plusdeg.size() == 1 && _4plusdeg_node_cnt == 1) {
assert(graphs_without_specific_nodes.size() == 1); // hack
for(auto [_, graph_without_the_only_4plusdeg] : graphs_without_specific_nodes) {
return info[graph_without_the_only_4plusdeg.excl_node].count_3deg_neighbors() == _3deg_node_cnt && !graph_without_the_only_4plusdeg.has_cycle_flag;
}
} else {
return 0;
}
} else if(components_with_3deg.size() > 0) {
//cout << "case 3\n";
if(components_with_3deg.size() == 1) {
int dsu_rep = *components_with_3deg.begin();
auto candidates = get_3deg_and_neighbors(dsu_rep);
int cnt = 0;
for(int cand : candidates) {
auto it = graphs_without_specific_nodes.find(cand);
assert(it != graphs_without_specific_nodes.end());
assert(it->second.excl_node == cand);
//cout << "candidate " << cand << ": " << info[cand].count_3deg_neighbors() << " + " << info[cand].is_3deg() << " == " << _3deg_node_cnt << " with cycle: " << it->second.has_cycle_flag << endl;
cnt += info[cand].count_3deg_neighbors() + info[cand].is_3deg() == _3deg_node_cnt && !it->second.has_cycle_flag;
}
return cnt;
} else {
return 0;
}
} else {
//cout << "case 2-\n";
if(components_with_cycle.size() == 0) {
return n;
} else if(components_with_cycle.size() == 1) {
return dsu.sz[*components_with_cycle.begin()];
} else {
return 0;
}
}
assert(false);
}
