Description

我们班共有n名同学，编号1至n。其中，有m对无话不说的好朋友。作为一对无话不说的好朋友，只要其中一个人知道了什么小秘密，就会立即告知另一个人。

现在，1号同学知道了一个小秘密，请问班上哪些同学会知道这个小秘密？此外，知道小秘密的同学分别都是通过几次消息传递知道这个秘密的？

Input Format

第一行包含两个正整数n、m，分别表示同学数量和朋友对数。

随后m行，每行包含两个正整数，表示一对朋友。

Output Format

请输出n行，每行一个整数。对于第i行的整数，若i号同学知道这个秘密，请输出它是通过几次消息传递知道这个秘密的；若i号同学不知道这个秘密，请输出-1。

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

0
1
1
2
3
-1

Hint

对于30%的数据，n<=100, m<=200；

对于60%的数据，n<=1000, m<=2000；

对于100%的数据，n<=100000, m<=200000。