Soccer

In soccer, there are many different rewards (and punishments) depending on how you rank in the league at the end of a season. For example, in the British Premier League, the top 4 teams are eligible to play in the Champions League, the next team is eligible to play in the Europa League, and the bottom three teams are relegated to the lower division. It is now near the end of the soccer season, and there are still a number of games to be played. For any given team, we wish to know what is the highest and lowest rank it can have at the end of the season.

For each game played, a team wins if it scores more goals than its opponent. A team loses a game if it scores fewer goals. When both teams score the same number of goals, we call it a draw. A team earns 3 points for each win, 1 point for each draw and 0 point for each loss. Teams are ranked according to the number of points earned (more points result in a higher ranking). Teams that are tied are given the same rank. For example, if two teams are tied and have the next highest point total after the 3rd place team, then they are both ranked 4th (and the next team is ranked 6th). In real life, factors such as goal differences and goals scored are used to break ties, but we will not consider these for this problem.

You are given a list of soccer teams and a list of matches in a season. You may assume that every team will play the same number of games at the end. Some of the matches have been played and the results are known.

The input consists of a number of cases. The first line in each case specifies two integers n and m (2≤n≤20, 1≤m≤1000) indicating the number of teams in the league and the number of matches in the season. The next n lines contain the name of each team in its own line. The team names contain only alphabetic characters and have lengths at most 30 characters. This is followed by m lines each of the form

team1 vs team2: x y

with team1 and team2 being the names of two different teams, and x and y are non-negative integers (or both are -1), indicating that in the game between team1 and team2, team1 scores x goals and team2 scores y goals. If both x and y are -1, then the game has not yet been played. At most 12 games will not have been played yet.

The input is terminated with n = m = 0.

For each team in the same order as the team list in the input, print one line of the following form:

Team XXX can finish as high as nth place and as low as mth place.

Use st, nd, and rd instead of th for first, second, and third place, respectively. Print a blank line between cases.

4 6
ManUnited
Arsenal
Chelsea
Tottenham
ManUnited vs Arsenal: 3 1
Chelsea vs Arsenal: 2 2
ManUnited vs Chelsea: 1 0
Tottenham vs ManUnited: -1 -1
Tottenham vs Chelsea: 0 4
Tottenham vs Arsenal: -1 -1
0 0

Team ManUnited can finish as high as 1st place and as low as 1st place.
Team Arsenal can finish as high as 2nd place and as low as 4th place.
Team Chelsea can finish as high as 2nd place and as low as 3rd place.
Team Tottenham can finish as high as 1st place and as low as 4th place.

HDOJ开放式进阶训练(11)——全程测试