H. Hurricane
time limit per test
2 s
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

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 \lt 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$$$.

Examples
Input
4 2
1 2
3 4
Output
4 2 0
Input
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Output
0 0 0