Soccer

Time limit2sMemory limit128 MB

Summary
Given a partial soccer schedule with at most 12 unplayed matches, find the best and worst final rank each team can still achieve. Ties share the same position.
Level

Hard8 of 10

Topics
Brute force, Implementation, Sorting, Combinatorics
Solved
No attempts yet

Problem

When the Premier League season ends, the final standings decide which teams qualify for European competitions and which are relegated. With only a few matches left, we want to determine the range of final positions each team can still end up in.

In a soccer match the team that scores more goals wins; if both teams score the same number of goals, the match is a draw. A win is worth 3 points, a draw is worth 1 point for each team, and a loss is worth 0 points. Teams are ranked by points only (unlike real soccer, goal difference and goals scored are not used). More points means a higher position, and teams with equal points share the same position. For example, if two teams are tied for 3rd, the next team by points is ranked 5th, not 4th.

Given the teams in the league and the match schedule (results of matches already played and matches not yet played), write a program that finds, for each team, the highest and lowest position it can finish in once the season is over.

Input

The input consists of several test cases. The first line of each test case contains the number of teams nn and the number of matches mm (2≤n≤202 \le n \le 20, 1≤m≤10001 \le m \le 1000).

The next nn lines each contain one team name. Team names consist only of letters and are at most 30 characters long.

The next mm lines describe the schedule and results in the following format:

team1 vs team2: x y

team1 and team2 are the names of two different teams, and x and y are non-negative integers giving the goals scored by team1 and team2, respectively. If both x and y are -1, that match has not been played yet. At most 12 matches are unplayed.

The input ends with a line in which both nn and mm are 0.

Output

For each test case, following the order in which the teams were given, print the highest and lowest position each team can finish in, using the following format:

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

For the ordinal suffix, use st for 1st place, nd for 2nd, rd for 3rd, and th for every other place. Print a blank line between the outputs of different test cases.

Hint

In the real Premier League, 20 teams play each other twice (home and away), but in this problem different teams may have played different numbers of matches.

Examples3

  1. Example 1

    Input
    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
    Expected output
    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.

  2. Example 2

    Input
    2 1
Alpha
Bravo
Alpha vs Bravo: 2 1
0 0
    Expected output
    Team Alpha can finish as high as 1st place and as low as 1st place.
Team Bravo can finish as high as 2nd place and as low as 2nd place.

  3. Example 3

    Input
    2 1
Alpha
Bravo
Alpha vs Bravo: -1 -1
0 0
    Expected output
    Team Alpha can finish as high as 1st place and as low as 2nd place.
Team Bravo can finish as high as 1st place and as low as 2nd place.