축구

프리미어리그 시즌이 끝나면 최종 순위에 따라 유럽 대회 진출권과 강등 여부가 결정된다. 리그가 몇 경기밖에 남지 않은 상황에서, 시즌이 끝났을 때 각 팀이 받을 수 있는 순위의 범위를 구하려고 한다.

축구 경기는 골을 더 많이 넣은 팀이 이기고, 두 팀의 득점이 같으면 비긴다. 이긴 팀은 승점 3점, 비긴 팀은 각각 1점, 진 팀은 0점을 얻는다. 순위는 오직 승점으로만 매긴다(실제 축구와 달리 골 득실과 득점 수는 사용하지 않는다). 승점이 높을수록 순위가 높고, 승점이 같은 팀은 같은 순위를 가진다. 예를 들어 어떤 두 팀이 공동 3위라면, 그다음으로 승점이 높은 팀의 순위는 4위가 아니라 5위이다.

리그에 속한 팀들과 경기 일정(이미 치른 경기의 결과와 아직 치르지 않은 경기)이 주어질 때, 각 팀이 시즌을 마쳤을 때 도달할 수 있는 가장 높은 순위와 가장 낮은 순위를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 팀의 수 $n$과 경기의 수 $m$이 주어진다 ($2 \le n \le 20$, $1 \le m \le 1000$).

다음 $n$개의 줄에는 팀 이름이 한 줄에 하나씩 주어진다. 팀 이름은 알파벳으로만 이루어지며 길이는 최대 30글자이다.

다음 $m$개의 줄에는 경기 일정과 결과가 다음 형식으로 주어진다.

team1 vs team2: x y

team1과 team2는 서로 다른 팀의 이름이고, x와 y는 각각 team1과 team2의 득점을 나타내는 음이 아닌 정수이다. x와 y가 모두 -1이면 그 경기는 아직 치르지 않은 것이다. 아직 치르지 않은 경기는 최대 12개이다.

입력은 $n$과 $m$이 모두 0인 줄로 끝난다.

각 테스트 케이스마다, 입력으로 주어진 팀 순서대로 각 팀이 도달할 수 있는 가장 높은 순위와 가장 낮은 순위를 다음 형식으로 출력한다.

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

순위 뒤의 서수 접미사는 1위는 st, 2위는 nd, 3위는 rd, 그 외의 순위는 모두 th를 사용한다. 서로 다른 테스트 케이스의 출력 사이에는 빈 줄을 하나 넣는다.

실제 프리미어리그에서는 20개 팀이 홈 앤 어웨이로 서로 두 번씩 경기하지만, 이 문제에서는 팀마다 치른 경기 수가 서로 다를 수 있다.