Футбол
В футболе существует множество различных наград (и наказаний) в зависимости от того, какое место команда занимает в лиге в конце сезона. Например, в Британской Премьер-лиге первые 4 команды получают право участвовать в Лиге чемпионов, следующая команда — в Лиге Европы, а три последние команды вылетают в низший дивизион. Сейчас сезон футбола близится к завершению, и еще предстоит сыграть несколько матчей. Для любой данной команды мы хотим определить, какое наивысшее и наинизшее место она может занять в конце сезона.
За каждый сыгранный матч команда побеждает, если забивает больше голов, чем ее соперник. Команда проигрывает матч, если забивает меньше голов. Когда обе команды забивают одинаковое количество голов, это называется ничьей. Команда зарабатывает 3 очка за каждую победу, 1 очко за каждую ничью и 0 очков за каждое поражение. Команды ранжируются в соответствии с количеством заработанных очков (больше очков — выше рейтинг). Команды, которые имеют одинаковое количество очков, получают одинаковый ранг. Например, если две команды имеют одинаковое количество очков и занимают следующее по величине количество очков после команды, занимающей 3-е место, то обе они занимают 4-е место (а следующая команда занимает 6-е место). В реальной жизни для разрешения ничьих используются такие факторы, как разница голов и количество забитых голов, но мы не будем их учитывать в этой задаче.
Вам дан список футбольных команд и список матчей в сезоне. Вы можете предположить, что каждая команда сыграет одинаковое количество игр в конце. Некоторые из матчей уже сыграны, и результаты известны.
Входные данные
Ввод состоит из нескольких случаев. Первая строка в каждом случае задает два целых числа n и m (2 ≤ n ≤ 20, 1 ≤ m ≤ 1000), указывающих количество команд в лиге и количество матчей в сезоне. Следующие n строк содержат имя каждой команды в отдельной строке. Имена команд содержат только алфавитные символы и имеют длину не более 30 символов. Далее следуют m строк, каждая из которых имеет вид
team1 vs team2: x y
где team1 и team2 — это имена двух разных команд, а x и y — неотрицательные целые числа (или оба равны -1), указывающие, что в игре между team1 и team2 команда team1 забила x голов, а команда team2 забила y голов. Если и x, и y равны -1, то игра еще не была сыграна. Не более 12 игр еще не были сыграны.
Ввод завершается строкой n = m = 0.
Выходные данные
Для каждой команды в том же порядке, что и в списке команд на входе, выведите одну строку следующего вида:
Team XXX can finish as high as nth place and as low as mth place.
Используйте st, nd и rd вместо th для первого, второго и третьего места соответственно. Напечатайте пустую строку между случаями.