#P1268E. Happy Cactus
Happy Cactus
No submission language available for this problem.
Description
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.
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.
Print $n$ integers, required values for vertices $1,2,\ldots,n$.
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$.
Samples
3 3
1 2
2 3
3 1
2 2 2
5 4
1 2
2 3
3 4
4 5
4 4 3 2 1