Problem 2: Rank Fraud, (K Narayan Kumar, CMI)
Our friend the king decided to rank his ministers based on their ability to play table-tennis. He did not want to rely on chance upsets, so he asked his prime minister to organize a competition in which every minister played every other minister.
Needless to say, at the end of the competition, each minister had won a few matches and lost a few matches, so there was no conclusive overall winner. Time was running out to deliver the results to the king and there was no time to organize a tie breaker. In a fit of inspiration, it occurred to the prime minister that if he could present the king with a list of names in which every minister had beaten the next minister in the list, the king would be satisfied that he had ranked the ministers in order of their abilities at table tennis.
For instance, suppose that the ministers were numbered 1, 2, 3, 4 and 5 and the results of the competition were as follows:
- Minister 1 beat ministers 2 and 4.
- Minister 2 beat minister 5.
- Minister 3 beat ministers 1 and 2.
- Minister 4 beat ministers 2, 3 and 5.
- Minister 5 beat ministers 1 and 3.
Then, the prime minister could present the following list to the king,
4 3 1 2 5,
because Minister 4 beat minister 3, who beat minister 1, who beat minister 2, who beat minister 5.
The problem to be solved is the following: Given the results of the competition, identify a winning sequence as described above, if such a sequence exists. There may be more than one such sequence. It is sufficient to find any one. If no such sequence exists, you should say that there is no solution.
The first line of input is the number of ministers N. The ministers are numbered 1,2,...,N.
Lines 2 to N+1 lines describe the performance of each of the N ministers in the tournament. Line i+1, describing the performance of minister i, looks like the following,
M P1 P2 ... PM
where M is the number of entries that follow on this line and P1, P2, ..., PM are the ministers whom minister i has beaten in the competition. This list is in an arbitrary order. Each minister plays every other minister exactly once. No draws are possible.
If a solution exists, the first line of the output consists of a single word YES. The following line must list out the ministers in the order required, separated by spaces. It is enough to print out any one solution, even if more than one solution exists. If no solution is possible, the output should consist of a single line with the word NO on it.
You may assume that 2 ≤ N ≤ 2000.
Here are some sample inputs and outputs corresponding to the examples discussed above.
5 2 4 2 1 5 2 2 1 3 2 5 3 2 3 1
YES 4 3 1 2 5
|CPU Timelimit:||3 seconds|