题目描述
Triangle War is a two-player game played on the following triangular grid:
Two players, A and B, take turns lling in any dotted line connecting two dots, with A starting rst.
Once a line is lled, it cannot be lled again. If the line lled by a player completes one or more triangles, she owns the completed triangles and she is awarded another turn (i.e. the opponent skips a turn). The game ends after all dotted lines are lled in, and the player with the most triangles wins the game. The di erence in the number of triangles owned by the two players is not important.
For example, if A lls in the line between 2 and 5 in the partial game on the left below:
Then, she owns the triangle labelled A and takes another turn to ll in the line between 3 and 5. B can now own 3 triangles (if he wishes) by lling in the line between 2 and 3, then the one between 5 and 6, and nally the one between 6 and 9. B would then make one more move before it is A's turn again.
In this problem, you are given a number of moves that have already been made. From the partial game, you should determine which player will win assuming that each player plays a perfect game from that point on. That is, assume that each player always chooses the play that leads to the best possible outcome for himself/herself.
Two players, A and B, take turns lling in any dotted line connecting two dots, with A starting rst.
Once a line is lled, it cannot be lled again. If the line lled by a player completes one or more triangles, she owns the completed triangles and she is awarded another turn (i.e. the opponent skips a turn). The game ends after all dotted lines are lled in, and the player with the most triangles wins the game. The di erence in the number of triangles owned by the two players is not important.
For example, if A lls in the line between 2 and 5 in the partial game on the left below:
Then, she owns the triangle labelled A and takes another turn to ll in the line between 3 and 5. B can now own 3 triangles (if he wishes) by lling in the line between 2 and 3, then the one between 5 and 6, and nally the one between 6 and 9. B would then make one more move before it is A's turn again.
In this problem, you are given a number of moves that have already been made. From the partial game, you should determine which player will win assuming that each player plays a perfect game from that point on. That is, assume that each player always chooses the play that leads to the best possible outcome for himself/herself. 输入
You will be given a number of games in the input. The rst line of input is a positive integer indicating the number of games to follow. Each game starts with an integer 6 <= m <= 18 indicating the number of moves that have been made in the game. The next m lines indicate the moves made by the two players in order, each of the form i j (with i < j) indicating that the line between i and j is lled in that move. You may assume that all given moves are legal.
输出
For each game, print the game number and the result on one line as shown below. If A wins, print the sentence \A wins." If B wins, print \B wins."
样例输入 Copy
4
6
2 4
4 5
5 9
3 6
2 5
3 5
7
2 4
4 5
5 9
3 6
2 5
3 5
7 8
6
1 2
2 3
1 3
2 4
2 5
4 5
10
1 2
2 5
3 6
5 8
4 7
6 10
2 4
4 5
4 8
7 8
样例输出 Copy
Game 1: B wins.
Game 2: A wins.
Game 3: A wins.
Game 4: B wins.