#include <bits/stdc++.h>
const int MAX_N = 1000000;
struct DSU {
int N;
int sef[MAX_N], grad[MAX_N], rank[MAX_N], size[MAX_N];
bool ignore[MAX_N];
enum ProblemState {
ONLY_CYCLES, // Am doar lanturi sau ciclii, tb doar sa vedem daca avem un singur ciclu
CRITICAL_NODES, // Am noduri de grade mai mari sau egale cu 3
// vedem ce se intampla daca excludem cate un nod critic, sa nu avem cicluri
// sau alte noduri cu grad mai mare ca 3
NOTHING // Raspunsul va fi 0 pentru totdeauna
} state;
int sizeCycle, cntCycle, gg3;
std::vector<std::pair<int*, int> > history;
std::vector<int> criticalNodes;
std::vector<std::pair<int, int> > edges;
std::vector<int> graph[MAX_N];
void setSize(int _N) {
state = ONLY_CYCLES;
N = _N;
reset();
}
void reset() {
for(int i = 0; i < N; ++i) {
sef[i] = i;
grad[i] = 0;
rank[i] = 0;
size[i] = 1;
}
sizeCycle = cntCycle = gg3 = 0;
}
int myfind(int x) {
if(sef[x] == x)
return x;
return myfind(sef[x]);
}
void initOnlyCyclesState(int firstCritical) {
criticalNodes.push_back(firstCritical);
ignore[firstCritical] = true;
for(auto it: graph[firstCritical]) {
criticalNodes.push_back(it);
ignore[it] = true;
}
reset();
state = CRITICAL_NODES;
for(auto it: edges)
link(it.first, it.second);
}
void addEdge(int a, int b) {
edges.push_back(std::make_pair(a, b));
graph[a].push_back(b);
graph[b].push_back(a);
}
void persistentModify(int* x, int y) {
history.push_back(std::make_pair(x, *x));
*x = y;
}
void link(int a, int b) {
int sa, sb;
sa = myfind(a);
sb = myfind(b);
if(rank[sa] < rank[sb]) {
std::swap(a, b);
std::swap(sa, sb);
}
if(!ignore[a] && !ignore[b]) {
if(state == ONLY_CYCLES) {
grad[a]++;
grad[b]++;
if(grad[a] > 2)
initOnlyCyclesState(a);
else if(grad[b] > 2)
initOnlyCyclesState(b);
else if(sa == sb) {
cntCycle++;
sizeCycle = size[sa];
if(cntCycle > 1)
state = NOTHING;
} else {
sef[sb] = sa;
rank[sa] = rank[sa] + (rank[sa] == rank[sb]);
size[sa] = size[sb] + size[sa];
}
} else if(state == CRITICAL_NODES) {
persistentModify(&grad[a], grad[a] + 1);
persistentModify(&grad[b], grad[b] + 1);
if(sa == sb)
persistentModify(&cntCycle, cntCycle + 1);
else {
persistentModify(&sef[sb], sa);
persistentModify(&rank[sa], rank[sa] + (rank[sa] == rank[sb]));
persistentModify(&size[sa], size[sb] + size[sa]);
}
if(grad[a] > 2)
persistentModify(&gg3, gg3 + 1);
if(grad[b] > 2)
persistentModify(&gg3, gg3 + 1);
}
}
}
int getTimeStamp() {
return history.size();
}
void revertTimestamp(int timestamp) {
while(history.size() > timestamp) {
*history.back().first = history.back().second;
history.pop_back();
}
}
void sanitizeCritical() {
std::vector<int> sanitized;
std::vector<int> badNodes;
std::vector<std::pair<int, int> > addedEdges;
for(int i = 0; i < criticalNodes.size(); ++i) {
addedEdges.clear();
int ts = getTimeStamp();
for(int j = 0; j < criticalNodes.size(); ++j)
if(i != j)
ignore[criticalNodes[j]] = false;
for(int j = 0; j < criticalNodes.size(); ++j)
if(i != j)
for(auto it: graph[criticalNodes[j]]) {
bool ok = true;
for(auto edge: addedEdges)
if(edge == std::make_pair(criticalNodes[j], it) ||
edge == std::make_pair(it, criticalNodes[j]))
ok = false;
if(ok) {
link(criticalNodes[j], it);
addedEdges.push_back(std::make_pair(it, criticalNodes[j]));
}
}
if(gg3 == 0 && cntCycle == 0)
sanitized.push_back(criticalNodes[i]);
else
badNodes.push_back(criticalNodes[i]);
for(int j = 0; j < criticalNodes.size(); ++j)
if(i != j)
ignore[criticalNodes[j]] = true;
revertTimestamp(ts);
}
criticalNodes = sanitized;
for(auto it: badNodes)
ignore[it] = false;
addedEdges.clear();
for(auto it: badNodes)
for(auto it2: graph[it]) {
bool ok = false;
for(auto edge: addedEdges)
if(edge == std::make_pair(it, it2) ||
edge == std::make_pair(it2, it))
ok = false;
if(ok) {
link(it, it2);
addedEdges.push_back(std::make_pair(it, it2));
}
}
if(criticalNodes.size() == 0)
state = NOTHING;
}
int getCriticalPoints() {
switch(state) {
case ONLY_CYCLES:
if(cntCycle == 0)
return N;
else if(cntCycle == 1)
return sizeCycle;
else
return 0;
case CRITICAL_NODES:
sanitizeCritical();
return criticalNodes.size();
case NOTHING:
return 0;
}
return 0;
}
} dsu;
void Init(int N_) {
dsu.setSize(N_);
}
void Link(int A, int B) {
dsu.addEdge(A, B);
dsu.link(A, B);
}
int CountCritical() {
int res = dsu.getCriticalPoints();
return res;
}
