Soccer#1806
In soccer, there are many different rewards (and punishments) depending on your rank in the league at the end of a season. For example, in the British Premier League, the top teams can play in the Champions League, the next team can play in the Europa League, and the bottom three teams are relegated. It is now near the end of the season, and there are still a number of games to be played. For any given team, we wish to know the highest and lowest rank it can have at the end of the season.
For each game, a team wins if it scores more goals than its opponent. A team loses if it scores fewer goals. When both teams score the same number of goals, it is a draw. Each win earns a team points, a draw earns point, and a loss earns points. Teams are ranked by total points (more points mean a higher ranking). Teams tied in points share the same rank. For example, if two teams are tied for the next highest point total after the rd place team, they are both th (and the next team is th). In real life, tiebreakers like goal difference are used, but we will not consider them here.
You are given a list of teams and a list of matches in the season. Assume that each team will play the same number of games by the end. Some games have already been played and results are known.
The input consists of several cases. Each case begins with a line containing two integers and (2 \leq n \leq 20, 1 \leq m \leq 1000): the number of teams and the number of matches. The next lines list the name of each team. Team names contain only alphabetic characters and have length at most . Then lines follow, each in the format
team1 vs team2: x y
where and are two different team names, and and are non-negative integers (or both ), indicating scored goals and scored goals. If both and are , the match has not yet been played. No more than matches are unplayed.
The input ends with n = m = 0.
For each team, in the same order as in the input, output a line in the following format:
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 places. Print a blank line between cases.
Example 1