#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back
#define ll long long
#define ui uint64_t
#define ar array
#define us unordered_set
#define cont(set, element) ((set).find(element) != (set).end())
/********* DEBUG *********/
template <typename T>
void outvec(const vector<T>& Z){
for (const T& x : Z)
cout << x << ' ';
cout << "\n";
}
void printVariable(const any& var) {
if (!var.has_value()) {
cout << "null";
return;
}
if (var.type() == typeid(int)) {
cout << any_cast<int>(var);
} else if (var.type() == typeid(double)) {
cout << any_cast<double>(var);
} else if (var.type() == typeid(float)) {
cout << any_cast<float>(var);
} else if (var.type() == typeid(char)) {
cout << any_cast<char>(var);
} else if (var.type() == typeid(bool)) {
cout << (any_cast<bool>(var) ? "true" : "false");
} else if (var.type() == typeid(string)) {
cout << any_cast<string>(var);
} else if (var.type() == typeid(const char*)) {
cout << any_cast<const char*>(var);
} else if (var.type() == typeid(long long)) {
cout << any_cast<long long>(var);
} else {
cout << "[unknown type]";
}
}
template<typename... Args>
void outval(Args... args) {
vector<any> variables = {args...};
for (size_t i = 0; i < variables.size(); ++i) {
printVariable(variables[i]);
if (i != variables.size() - 1) {
cout << " ";
}
}
cout << "\n";
}
#define nl "\n"
#define sp << " " <<
/********* DEBUG *********/
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
const ll MOD3 = 1000000000;
const ll needMOD = 987654321;
const ll mxN = 1000005;
const ll inf = 1e18;
/* Thoughts
Cases where there are no criticals:
- Two unconnected nodes that don't share any neighbours
- Two unconnected cycles
- One cycle AND node outside cycle has 3 or more edges that aren't in cycle
Cases for criticals
1. Cycles
- When there is one cycle, critical can only be inside the cycle.
- If there is a node with 3 or more neighbours, only nodes with 3 or more
neighbours in the cycle are critical
*/
/* Implementation
DSU keep track of cycles, every Link() union A and B,
if there is a cycle only nodes in cycle can be removed,
if there is two cycles only one crtitical node maximum can be removed
have to remove all nodes with indegree >= 3, else ans is 0
Keep track of ind >= 3 cnt, also keep track of their nodes,
*/
// parent of nd i
vector<ll> pars(mxN), cycleCnt(mxN);
// candidates that need and can be removed
set<int> cands;
set<ll> out;
vector<vector<ll>> adj(mxN);
// amount of critical nodes, current N, amount of cycles, amount of ind3s to remove, need par to be for cand
ll crits, currN, cycles, needremove, cyccheck;
bool cycled = false;
// DSU
ll findP(ll x){
if (pars[x] == x)
return x;
return pars[x] = findP(pars[x]);
}
void uni(ll x, ll y){
x = findP(x);
y = findP(y);
pars[x] = y;
}
void Init(int N){
cycled = false;
crits=N;
cyccheck=false;
cycles=needremove=0;
currN=N;
for (int i = 0; i < N; i++){
cycleCnt[i]=0;
pars[i]=i;
adj[i].clear();
}
}
bool dfs(ll nd, ll fnd, ll skip, unordered_set<ll> &seen, ll par = -1){
//outval("cl");
if (nd == fnd && par != -1)
return true;
if (cont(seen, nd))
return false;
if (nd!=fnd)
seen.insert(nd);
bool win = false;
for (auto x : adj[nd]){
if (cycleCnt[x] == 0 || x == par || x == skip || cont(seen, x))
continue;
win = win | dfs(x, fnd, skip, seen, nd);
}
return win;
}
// bfs to cnt cycles
void bfs(ll a, ll b){
unordered_map<ll, ll> prev;
queue<ll> q;
q.push(a);
prev[a] = -1;
while (q.size()){
ll curr = q.front(); q.pop();
for (auto x : adj[curr]){
if (x == prev[curr])
continue;
if (x == b){
++cycleCnt[x];
if (cycles == 1 && needremove == 0)
crits++;
while (curr != -1){
++cycleCnt[curr];
if (1 == cycles && needremove == 0)
crits++;
curr=prev[curr];
}
return;
}
if (prev.find(x) == prev.end()){
prev[x] = curr;
q.push(x);
}
}
}
}
void Link(int A, int B){
if (crits == 0)
return;
if (findP(A) == findP(B)){
cycles++;
if (cycles == 1)
crits = 0;
cyccheck = true;
if (cycles <= 2)
bfs(A,B);
}
// base case hunting
if (needremove == 0 && cycles > 1){
crits = 0;
return;
}
// if (needremove >= 3 && cycles >= 2){
// crits = 0;
// return;
// }
// if (needremove >= 2 && cycles >= 3){
// crits = 0;
// return;
// }
uni(A,B);
adj[A].pb(B);
adj[B].pb(A);
if (sz(adj[A]) == 3){
needremove++;
if (!cycled){
if (cycles){
out.clear();
for (auto &x : adj[A]){
if (cycleCnt[x] == cycles)
out.insert(x);
}
cands.clear();
for (auto &x : out)
cands.insert(x);
}
cycled = true;
}
cands.insert(A);
for (auto &x : adj[A]){
cands.insert(x);
}
}
if (sz(adj[B]) == 3){
needremove++;
if (!cycled){
if (cycles){
out.clear();
for (auto &x : adj[B]){
if (cycleCnt[x] == cycles)
out.insert(x);
}
cands.clear();
for (auto &x : out)
cands.insert(x);
}
cycled = true;
}
cands.insert(B);
for (auto &x : adj[B]){
cands.insert(x);
}
}
//outval("nremove:",needremove);
if ((needremove || sz(cands) || crits != currN || cycles) && (cycles > 1 || needremove))
crits = sz(cands);
unordered_set<ll> seen;
out.clear();
if (needremove)
for (auto &x : cands){
seen.clear();
bool flag = false;
ll remove = (sz(adj[x]) >= 3);
if (cycleCnt[x] != cycles && cycles < 3){
out.insert(x);
continue;
}
for (auto &y : adj[x]){
if (cyccheck && !cont(seen,y) && cycled && dfs(y,y,x,seen)){
flag=true; out.insert(x); break;
}
if (sz(adj[y]) == 3)
remove++;
}
if (flag)
continue;
if (needremove - remove > 0)
out.insert(x);
}
if (cyccheck)
cyccheck = false;
for (auto &x : out)
cands.erase(x);
if ((needremove || sz(cands) || crits != currN || cycles) && (cycles > 1 || needremove))
crits = sz(cands);
// cout << "cands: ";
// for (auto &x : cands)
// cout << x << ' ';
// cout << "\n";
}
int CountCritical(){
return crits;
}
