問題文

N 頂点 M 辺の無向グラフが与えられます。各頂点には 1 から N までの番号が付けられており、i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。

1 以上 N 以下の全ての整数 k について、以下の問いに答えてください。

頂点 1 から頂点 k まで、辺を何本かたどって移動することを考えるとき、たどるべき辺の本数の最小値を出力せよ。ただし、移動不可能な場合は -1 を出力せよ。

制約

• 入力はすべて整数
• 1 \le N \le 10^5
• 0 \le M \le \min(10^5,\frac{N(N-1)}{2})
• 1 \le A_i < B_i \le N
• グラフに多重辺や自己ループは存在しない

入力例 1

3 2
1 3
2 3

出力例 1

0
2
1

• 頂点 1 から頂点 1 には、 0 本の辺を辿って移動可能であるとします。
• 頂点 1 から頂点 2 に移動する際、 1 \rightarrow 3 \rightarrow 2 と移動すると辿る辺の数が最小になります。
• 頂点 1 から頂点 3 に移動する際、 1 \rightarrow 3 と移動すると辿る辺の数が最小になります。

入力例 2

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

出力例 2

0
1
2
1
-1
-1

与えられるグラフが連結であるとは限りません。