[[Category: BFS]]
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:
Your job is to write a program to compute Giovanni numbers.
The input begins with a single positive integer k ≤ 100 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 (2 ≤ P ≤ 105 and 0 ≤ D ≤ 106) 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.
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. If the Giovanni number is ∞, print ``INF". Note that it is P-1 because we skip Don Giovanni in the output.