The European Football Championship is coming! From the 12th of June to the 4th of July, Portugal will be the sports center of the world. Everyone will do their best to make this event a memorable one. However, an important detail is missing. The rules for the classification of the league stage have changed and everyone is a little bit confused. What would be really, really nice would be a computer program to calculate this classification, given the results of the game. Then it would also be possible to watch in real time the changes in the ranking! Here is how the classification is made:
2/3 It is not necessary that games between all the teams have been made. Of course that you should only calculate the classification based on the games that you were given. Also, some teams may play against each other more than one time. To make the classification you should consider all the teams that played at least one game. You may assume that the number of teams is ≤ 10000 Output The output for each test case consists of lines in the form “PLACE TEAM”, in ascending order of place, where PLACE indicates the place the team got and TEAM is the name of the team. Remember that all teams that played at least one game must appear. Output of different test cases should be separated by a single blank line. See the example output for a more detailed explanation of how the classification was obtained on that particular cases. Explanation of Sample I/O: • First sample case: Looking at the games, we see that “portugal”, “espanha” and “grecia” made 6 points, and “russia” made 0 points (which automatically gives them the 4th place). A tie between the first three teams is achieved. A sub-league with only that three teams is then considered but in this sub-league all the three teams have 3 points. This tied group cannot be partitioned further and then the other parameters are considered. Since in that sub-league, “portugal” has the best goal- average, it achieves 1st place. Then comes “espanha” (2nd goal-average) and finally “grecia”. If necessary, the other parameters would have been taken in account. • Second sample case: Now, “portugal” and “grecia” are tied with 6 points, and “espanha” and “russia” have 3 points. The sub-league between “portugal” and “grecia” unties the two teams (“portugal” won against “grecia”), and in the same way the sub-league between “espanha” and “russia” unties them. • Third sample case: The only two teams tied the game, so they are equal in all parameters. They are in the same place and they appear in alphabetical order. Sample Input 3 6 portugal grecia 4 1 espanha russia 3 1 portugal russia 3 0 espanha grecia 1 2 portugal espanha 1 3 grecia russia 7 0 6 portugal grecia 4 1 espanha russia 1 3 portugal russia 3 0 espanha grecia 1 2 portugal espanha 1 3
3/3 grecia russia 7 0 1 brasil franca 0 0 Sample Output 1 portugal 2 espanha 3 grecia 4 russia 1 portugal 2 grecia 3 russia 4 espanha 1 brasil 1 franca