삼각형 전쟁

삼각형 전쟁은 다음 삼각형 격자 위에서 하는 2인용 게임이다.

두 명의 플레이어 A와 B가 번갈아 가며 두 점을 잇는 점선 중 하나를 채우며, A가 먼저 시작한다. 한 번 채운 선은 다시 채울 수 없다. 어떤 플레이어가 채운 선이 하나 이상의 삼각형을 완성하면, 그 플레이어가 완성된 삼각형들을 차지하고 한 번 더 둔다(상대는 그 차례를 건너뛴다). 모든 점선이 채워지면 게임이 끝나고, 삼각형을 더 많이 차지한 플레이어가 이긴다. 두 플레이어가 차지한 삼각형 수의 차이는 중요하지 않다.

예를 들어, 아래 왼쪽의 진행 중인 게임에서 A가 2번과 5번 점 사이의 선을 채운다고 하자.

그러면 A는 A라고 표시된 삼각형을 차지하고, 한 번 더 두어 3번과 5번 점 사이의 선을 채운다. 이제 B는 원한다면 2번과 3번 사이, 그다음 5번과 6번 사이, 마지막으로 6번과 9번 사이의 선을 채워 삼각형 3개를 차지할 수 있다. 그런 다음 B는 A의 차례가 다시 오기 전에 한 번 더 둔다.

이 문제에서는 이미 진행된 몇 개의 수가 주어진다. 이 진행 중인 게임에서, 그 시점부터 두 플레이어가 모두 완벽하게 둔다고 가정할 때 어느 플레이어가 이기는지 판정하여라. 즉, 각 플레이어는 항상 자신에게 가장 좋은 결과로 이어지는 수를 선택한다.

입력의 첫 줄은 이어지는 게임의 수를 나타내는 양의 정수이다. 각 게임은 그 게임에서 이미 둔 수의 개수를 나타내는 정수 $m$ ($6 \le m \le 18$)으로 시작한다. 이어지는 $m$개의 줄에는 각각 한 수가 순서대로 i j ($i < j$) 형태로 주어지며, 이는 그 수에서 점 $i$와 점 $j$ 사이의 선을 채웠음을 뜻한다. 주어지는 모든 수는 규칙에 맞다고 가정해도 된다.

각 게임에 대해, 한 줄을 출력한다. A가 이기면 Game k: A wins.를, B가 이기면 Game k: B wins.를 출력한다. 여기서 k는 게임의 번호이며 첫 게임이 1이다.