토너먼트 순위 매기기

여러 팀이 참가하는 토너먼트에서, 두 팀씩 맞붙어 치른 경기의 결과가 주어진다. 팀은 좋아하는 종목에 따라 축구팀, 볼링팀, 농구팀 등 무엇이든 될 수 있다. 각 팀은 하나의 대문자로 구분하며, 팀은 최대 26개이다.

당신의 임무는 가능하다면 팀들의 순위를 매기는 것이다. 즉, 팀 사이의 경기 결과를 이용해 가장 강한 팀부터 가장 약한 팀까지 한 줄로 늘어놓은 순위표를 만들어야 한다. 팀 A가 팀 B를 이겼다면 A는 항상 B보다 강하다고 가정하며, 다시 B가 C를 이겼다면 A는 C보다도 강하다. 따라서 이러한 결과가 주어지면 순위는 A B C가 된다. 단, 올바른 순위를 항상 만들 수 있는 것은 아니다. 만약 C가 다시 A를 이긴다면 팀들의 순위를 정할 수 없다.

당신이 할 일은 올바른 순위를 출력하거나, 그런 순위가 존재하지 않음을 판단하는 것이다. 두 팀의 순서를 경기 결과만으로 결정할 수 없을 때는, 알파벳에서 더 앞선 팀을 먼저 나열한다. 즉 A를 B보다 앞에 두며, 그 결과로 사전순으로 가장 앞서는(가장 작은) 순위표를 출력한다. 예를 들어 B C A D를 C A B D보다 우선한다.

첫 줄에는 순위를 매겨야 할 토너먼트의 개수가 주어진다. 각 토너먼트마다 먼저 한 줄에 팀의 수와 치른 경기의 수가 주어진다. 팀은 A부터 시작해 알파벳 순서대로 이름이 붙는다고 가정해도 된다. 이어서 각 경기마다 한 줄에 대문자 두 개가 공백 하나로 구분되어 주어지며, 두 글자는 각각 그 경기의 승자와 패자를 (이 순서대로) 나타낸다.

각 토너먼트에 대해, 모든 팀을 한 줄에 순위 순서대로 출력한다. 각 팀은 자신의 올바른 위치에 정확히 한 번씩만 나타나며, 인접한 두 팀의 글자 사이에는 공백 하나를 둔다. 순위를 매기는 것이 불가능하면 No legal ranking possible을 출력한다.