Publication
The Orizondo number is a way of describing the "collaborative distance" between a scientist and Rodrigo Orizondo by authorship of scientific publications.
Rodrigo Orizondo is the only person who has an Orizondo number equal to zero. To be assigned a finite Orizondo number, a scientist must publish a paper in co-authorship with a scientist with a finite Orizondo number. The Orizondo number of a scientist is the lowest Orizondo number of his coauthors + 1. The order of publications and numbers assignment doesn't matter, i.e., after each publication the list of assigned numbers is updated accordingly.
You will be given the publications, each element of which describes the list of authors of a single publication and is formatted as "AUTHOR_1 AUTHOR_2 ... AUTHOR_N" (quotes for clarity only). Rodrigo Orizondo will be given as "ORIZONDO".
Print out the list of Orizondo numbers which will be assigned to the authors of the listed publications. Each element of the printout should be formatted as "AUTHOR NUMBER" if AUTHOR can be assigned a finite Orizondo number, and just "AUTHOR" otherwise. The authors in the printout list must be ordered lexicographically.
Input
The first line of the input gives the number of test cases C (0 < C ≤ 10,000).
Each test case starts with an integer N, the number of publications, then N publications follow. Each publication consists in a space separated list of authors.(each publication in a single line).
Notes |
|
| - | All authors mentioned in the list must be present in output. |
| - | Assume that all publications of mentioned authors are given in publications. |
| - | String S is lexicographically before string T if S is a proper prefix of T, or if S has an earlier character at the first position where the strings differ. |
Constraints |
|
| - | publications will contain between 1 and 50 elements, inclusive. |
| - | Each element of publications will contain between 1 and 50 characters, inclusive. |
| - | An author is a string of between 1 and 50 uppercase letters ('A'-'Z'), inclusive. |
| - | Each element of publications will be a list of authors, separated by single spaces. |
| - | Each element of publications will not have any trailing spaces. |
| - | The authors in each element of publication will be distinct. |
| - | There will be at most 100 distinct authors in all publications. |
| - | Rodrigo Orizondo will be given as "ORIZONDO", and at least one publication will list him as one of the authors. |
Output
For each test case, output one line containing each author with his Orizondo Number, all space separated.
Example
Input: 3
1
ORIZONDO
2
KLEITMAN LANDER
ORIZONDO KLEITMAN
4
ORIZONDO B
A B C
B A E
D F
Output:
ORIZONDO 0
KLEITMAN 1 LANDER 2 ORIZONDO 0
A 2 B 1 C 2 D E 2 F ORIZONDO 0