The Party, Part I

Don Giovanni likes to dance--especially with girls! And everyone else in the party enjoyed the dance, too. Getting a chance to dance with the host (that is Don Giovanni) is the greatest honour; failing that, dancing with someone who has danced with the host or will dance with the host is the second greatest honour. This can go further. Define the Giovanni number of a person as follows, at the time after the party is over and therefore who has danced with whom is completely known and fixed:

  1. No one has a negative Giovanni number.
  2. The Giovanni number of Don Giovanni is 0.
  3. If a person p is not Don Giovanni himself, and has danced with someone with Giovanni number n, and has not danced with anyone with a Giovanni number smaller than n, then p has Giovanni number n+1.
  4. If a person's Giovanni number cannot be determined from the above rules (he/she has not danced with anyone with a finite Giovanni number), his/her Giovanni number is tex2html_wrap_inline98. Fortunately, you will not need this rule in this problem.
Your job is to write a program to compute Giovanni numbers.

Input

The first line has two numbers P and D; this means there are P persons in the party (including Don Giovanni) and D dancing couples (tex2html_wrap_inline108 and tex2html_wrap_inline110.) Then D lines follow, each containing two distinct persons, meaning the two persons has danced. Persons are represented by numbers between 0 and P-1; Don Giovanni is represented by 0.

As noted, we design the input so that you will not need the tex2html_wrap_inline98 rule in computing Giovanni numbers.

We have made our best effort to eliminate duplications in listing the dancing couples, e.g., if there is a line ``4 7'' among the D lines, then this is the only occurrence of ``4 7'', and there is no occurrence of ``7 4''. But just in case you see a duplication, you can ignore it (the duplication, not the first occurrence).

Output

Output P-1 lines. Line i is the Giovanni number of person i, for tex2html_wrap_inline126. Note that it is P-1 because we skip Don Giovanni in the output.

Sample Input

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

Sample Output

1
1
2
2


Solution in Java
Solution in C++
Test Input 0/Test Output 0
Test Input 1/Test Output 1
Test Input 2/Test Output 2