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 ∞. Fortunately, you will not need this rule in this problem. Your job is to write a program to compute Giovanni numbers. Input The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. 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 (P ≤ 1000 and D ≤ P (P − 1)/2.) 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 ∞ 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 For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. Output P −1 lines. Line i is the Giovanni number of person i, for 1 ≤ i ≤ P −1. Note that it is P − 1 because we skip Don Giovanni in the output. Sample Input 1 56 01 02

2/2 32 24 43 12 Sample Output 1 1 2 2