시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 1 1 100.000%

문제

You are given a number of teams and the results of games played by pairs of these teams in a tournament. The teams could be football teams, bowling teams, basketball teams, depending on your favorite sport. Each team will be identified by an upper case letter. The maximum number of teams is 26.

Your mission is to rank the teams if possible. For this you are given results from games played between the teams, i.e., you should produce a linearly ordered list starting with the best team, and progressing down to the worst one. We assume that if team A beats team B then team A is always better than team B and if team B in its turn beats team C then team A is also better than team C. Thus given the above results the teams would be ranked A B C. Note that it might not always be possible to produce a legal ranking: if team C again beats team A then it is not possible to rank the teams.

Your job is to produce a legal ranking or to determine that no such ranking exists. If you cannot determine the order of two teams then the lexicographically largest should be listed first, i.e. A should be listed before B, and the lexicographically largest ordering should be prefferred, i.e. B C A D should be prefferred before C A B D.

입력

First there will be a line containing the number of tournaments you are asked to rank. For each tournament there will first be a line containing the number of teams and the number of games played. You may assume that the teams are named consecutively starting from A. For each game there will be a line containing two upper case letters, separated by one blank space. The two letters on a line indicate the winner and loser (in that order) of a game played by the two teams.

출력

The output will list all teams on one line, with each team appearing only once in its correct position. There should be one blank space between adjacent letters representing the teams. If no ranking is possible your program should print No legal ranking possible.

 

예제 입력

2
4 4
A B
B D
C D
A C
3 3
A B
B C
C A

예제 출력

A B C D
No legal ranking possible

힌트