1091: Who Has Highest Priority?

An operating system exploits the hardware resources of one or more processors to provide a set of services to system users. Accordingly, it is important to have some understanding of the underlying computer system hardware as we begin our examination of operating systems. Each process has a unique process ID, which was an integer from 1 to 100. For each list, process ID of the processes was written in a column according to their place in that list. IDs of the processes that had equal priority were written on the same line. The list started with the process(es) that has(have) highest priority in that list and continued as to the decreasing priority. The process has place K in the list if exactly K-1 processes were prior to it in that list. Consider the following example of two lists: The overall rating of the processes that appeared in both lists is defined as following: If a process is prior to another process in both two lists, it is prior to the latter overall, too. Otherwise, their overall rating depends on the difference of their places in both lists. As in our example, process 1 is prior to process 5 in the first list with 3 places difference and lower in another with 1 place difference, therefore the overall rating of process 1 is higher than process 5’s. In our example only process 1, 4, 5, and 9 appeared twice. Process 1 has the highest priority, process 5 and 9 with equal priority follow, and process 4 has the lowest one. For the processes that appeared in only one list their position in the resulting list can not be always determined. They are included in the overall list (where the processes which appeared twice already placed according to the rules above) if one of the following takes place: (Rule A) If a process that appeared in both lists shared the place in one list with a process in question, the latter shares the overall rating with it. If more than one such process, they should have the same overall rating, or the overall rating of the process in question cannot be determined. (Rule B) If there is a position in the overall list, such that before it only processes prior to the process in the same list located and after it only process lower in same list located, the process in question occupies this position in the overall list. If more than one process claim to have the same position in the overall list, then their mutual order is defined by their places in their lists. As the above, the positions of processes 6 and 7 can not be determined. As to rule A, process 10 will share the overall rating with process 1 while process 20 being with process 4. As to rule B, process 3 will occupy the first place in the overall list, process 19 will occupy the position between processes 5,9 and process 4, and, what’s more, processes 8,15,17,18,21, and 31 will finish the overall list in the end. But the first of them will be process 8 and 15 (that took 6th place) followed by process 18 and 31 (that took 8th place) and process 17 and 21 (that took 10th place).

The input contains several blocks, which are separated by an empty line. Each block starts with a line containing a single integer N (2<=N<=100) that indicates how many lines of the list table follow, and while N=0 means the end of the input. Each of N lines follow it starts with an integer T (1≤T≤N), indicates how many processes share the place excluding it, and then T processes’ id separated by spaces follows it. You may assume that every process identifier occurs at most once in each list of every block.

For every block, first write the block number and then write one or more lines with the process identifiers separated by spaces that represent the overall rating list. The order of the processes that share the same rating (thus written on the same line) is unimportant. The processes for which the overall rating is not determined should be absent in the output. Write an empty line after every block.

6
1 9
3 7 1 4
1 5
2 15 8
2 31 18
1 17
8
1 3
1 5
2 1 10
1 6
1 9
1 19
2 4 20
1 21

0
0

Priority of processes 1
3
1 10
9 5
19
4 20
8 15
18 31
21 17