Hurricane
Description
Byteland has $n$ cities numbered from $1$ to $n$, and $\frac{n(n-1)}{2}$ two-way roads connecting all pairs of cities directly. However, $m$ roads become impassable due to the recent severe hurricane.
To assess the disaster damage, you are asked to calculate the number of pairs of cities that the minimum number of roads on the paths containing only passable roads between the two cities is exactly $k$, for each $k = 1, 2, \ldots, n - 1$. Note that the pairs of cities that are not connected with passable roads should not be counted.
The first line contains two integers $n$ and $m$ ($2 \le n \le 100\,000$, $0 \le m \le \min\left(\frac{n(n-1)}{2}, 200\,000\right)$) indicating the number of cities and the number of impassable roads in Byteland.
Each of the following $m$ lines contains two integers $u$ and $v$ ($1 \le u < v \le n$) indicating that a road connecting cities $u_i$ and $v_i$ becomes impassable. It is guaranteed that each road appears at most once.
Output a single line containing $(n-1)$ integers, the $k$-th of which indicates the number of pairs of cities that the minimum number of roads on the paths between the two cities is exactly $k$.
Input
The first line contains two integers $n$ and $m$ ($2 \le n \le 100\,000$, $0 \le m \le \min\left(\frac{n(n-1)}{2}, 200\,000\right)$) indicating the number of cities and the number of impassable roads in Byteland.
Each of the following $m$ lines contains two integers $u$ and $v$ ($1 \le u < v \le n$) indicating that a road connecting cities $u_i$ and $v_i$ becomes impassable. It is guaranteed that each road appears at most once.
Output
Output a single line containing $(n-1)$ integers, the $k$-th of which indicates the number of pairs of cities that the minimum number of roads on the paths between the two cities is exactly $k$.
4 2
1 2
3 4
4 6
1 2
1 3
1 4
2 3
2 4
3 4
4 2 0
0 0 0