Happy Cactus

You are given a cactus graph, in this graph each edge lies on at most one simple cycle.

It is given as $m$ edges $a_i, b_i$, weight of $i$-th edge is $i$.

Let’s call a path in cactus increasing if the weights of edges on this path are increasing.

Let’s call a pair of vertices $(u,v)$ happy if there exists an increasing path that starts in $u$ and ends in $v$.

For each vertex $u$ find the number of other vertices $v$, such that pair $(u,v)$ is happy.Input

The first line of input contains two integers $n,m$ ($1 \leq n, m \leq 500\,000$): the number of vertices and edges in the given cactus.

The next $m$ lines contain a description of cactus edges, $i$-th of them contain two integers $a_i, b_i$ ($1 \leq a_i, b_i \leq n, a_i \neq b_i$).

It is guaranteed that there are no multiple edges and the graph is connected.Output

Print $n$ integers, required values for vertices $1,2,\ldots,n$.Examplesinput

3 3
1 2
2 3
3 1

output

2 2 2 

input

5 4
1 2
2 3
3 4
4 5

output

4 4 3 2 1 

Solution:

#include <bits/stdc++.h>

using namespace std;

template <typename T>
class graph {
public:
struct edge {
int from;
int to;
T cost;
};

vector<edge> edges;
vector<vector<int>> g;
int n;

graph(int _n) : n(_n) {
g.resize(n);
}

virtual int add(int from, int to, T cost) = 0;
};

template <typename T>
class undigraph : public graph<T> {
public:
using graph<T>::edges;
using graph<T>::g;
using graph<T>::n;

undigraph(int _n) : graph<T>(_n) {
}

int add(int from, int to, T cost = 1) {
assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int) edges.size();
    g[from].push_back(id);
    g[to].push_back(id);
    edges.push_back({from, to, cost});
    return id;
  }
};

template <typename T>
vector<vector<int>> find_cycles(const graph<T> &g, int bound_cnt = 1 << 30, int bound_size = 1 << 30) {
  vector<int> was(g.n, -1);
vector<int> st;
vector<vector<int>> cycles;
int total_size = 0;
function<void(int, int)> dfs = [&](int v, int pe) {
if ((int) cycles.size() >= bound_cnt || total_size >= bound_size) {
return;
}
was[v] = (int) st.size();
for (int id : g.g[v]) {
if (id == pe) {
continue;
}
auto &e = g.edges[id];
int to = e.from ^ e.to ^ v;
if (was[to] >= 0) {
vector<int> cycle(1, id);
for (int j = was[to]; j < (int) st.size(); j++) {
          cycle.push_back(st[j]);
        }
        cycles.push_back(cycle);
        total_size += (int) cycle.size();
        if ((int) cycles.size() >= bound_cnt || total_size >= bound_size) {
return;
}
continue;
}
if (was[to] == -1) {
st.push_back(id);
dfs(to, id);
st.pop_back();
}
}
was[v] = -2;
};
for (int i = 0; i < g.n; i++) {
    if (was[i] == -1) {
      dfs(i, -1);
    }
  }
  return cycles;
  // cycles are given by edge ids, all cycles are simple
  // breaks after getting bound_cnt cycles or total_size >= bound_size
// digraph: finds at least one cycle in every connected component (if not broken)
// undigraph: finds cycle basis
}

template <typename T>
vector<int> edges_to_vertices(const graph<T> &g, const vector<int> &edge_cycle) {
int sz = (int) edge_cycle.size();
vector<int> vertex_cycle;
if (sz <= 2) {
    vertex_cycle.push_back(g.edges[edge_cycle[0]].from);
    if (sz == 2) {
      vertex_cycle.push_back(g.edges[edge_cycle[0]].to);
    }
  } else {
    for (int i = 0; i < sz; i++) {
      int j = (i + 1) % sz;
      auto &e = g.edges[edge_cycle[i]];
      auto &other = g.edges[edge_cycle[j]];
      if (other.from == e.from || other.to == e.from) {
        vertex_cycle.push_back(e.to);
      } else {
        vertex_cycle.push_back(e.from);
      }
    }
  }
  return vertex_cycle;
  // only for simple cycles!
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
undigraph<int> g(n);
for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
--x; --y;
g.add(x, y);
}
vector<vector<int>> cycles = find_cycles(g);
vector<vector<int>> events(m);
for (auto& cycle : cycles) {
int sz = (int) cycle.size();
int pos = (int) (min_element(cycle.begin(), cycle.end()) - cycle.begin());
rotate(cycle.begin(), cycle.begin() + pos, cycle.end());
pos = (int) (max_element(cycle.begin(), cycle.end()) - cycle.begin());
bool ok = true;
for (int i = 0; i < pos - 1; i++) {
      if (cycle[i] > cycle[i + 1]) {
ok = false;
break;
}
}
for (int i = pos; i < sz - 1; i++) {
      if (cycle[i] < cycle[i + 1]) {
        ok = false;
        break;
      }
    }
    if (ok) {
      events[cycle[pos]].push_back(cycle[0]);
    }
  }
  vector<int> sub(m, 0);
vector<int> ans(n, 1);
for (int i = m - 1; i >= 0; i--) {
auto& e = g.edges[i];
int x = e.from;
int y = e.to;
int cur = ans[x] + ans[y] - sub[i];
ans[x] = ans[y] = cur;
for (int j : events[i]) {
sub[j] += cur;
}
}
for (int i = 0; i < n; i++) {
    if (i > 0) {
cout << " ";
    }
    cout << ans[i] - 1;
  }
  cout << '\n';
  return 0;
}