Byteland 有 $n$ 座城市，编号为 $1$ 到 $n$，且原本有 $\frac{n(n-1)}{2}$ 条双向道路直接连接每一对城市。然而，由于近期严重的飓风，有 $m$ 条道路变得无法通行。

为了评估灾害损失，你需要计算对于每个 $k = 1, 2, \dots, n - 1$，在仅包含可通行道路的情况下，两座城市之间最短路径长度恰好为 $k$ 的城市对数量。注意，无法通过可通行道路连接的城市对不应计入统计。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 100\,000$, $0 \le m \le \min(\frac{n(n-1)}{2}, 200\,000)$)，分别表示城市数量和无法通行的道路数量。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u < v \le n$)，表示连接城市 $u$ 和 $v$ 的道路变得无法通行。保证每条道路最多出现一次。

输出格式

输出一行，包含 $(n - 1)$ 个整数，其中第 $k$ 个整数表示两座城市间最短路径长度恰好为 $k$ 的城市对数量。

样例

输入格式 1

4 2
1 2
3 4

输出格式 1

4 2 0

输入格式 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

输出格式 2

0 0 0