Optimal Game Strategy Verification

Two players A and B play a game on a convex polygon with (n) vertices. Initially, A has a triangulation of the polygon, i.e. a set of (n-3) non‐intersecting diagonals that partition the polygon into triangles. In each move, player B may query a diagonal connecting two non-adjacent vertices (x) and (y), and A replies whether that diagonal is present in his current triangulation. B’s goal is to obtain at least one affirmative answer (i.e. a “yes”) for every diagonal that is part of A’s final triangulation. B wants to minimize the total number of queries, while A wants to maximize them by (possibly) changing his triangulation as the game proceeds. However, A must never contradict any of his previous answers.

Suppose that under optimal play B must ask exactly (k) queries. Then after every move the optimal strategies available to both players guarantee that the total number of queries is still (k). The very first move that causes the eventual number of required queries to differ from (k) is considered non-optimal. If the two players play optimally the game process is said to remain optimal.

Given the record of moves in one game, your task is to determine whether the game process remains optimal. If it is optimal, output 0; if not, output the first non-optimal move in the format A x or B x, where (x) is the count of moves made so far by that particular player (i.e. the first non-optimal move by A or B).

This problem involves simulating the evolution of strategies under the invariant that the total (optimal) number of queries remains (k) after every move. Note that until the first non-optimal move, A’s answers are guaranteed to be consistent with some triangulation, although they might become inconsistent after the first deviation.

inputFormat

The input begins with an integer (T) denoting the number of games. For each game, the first line contains two integers (n) and (m) — the number of vertices of the polygon and the number of moves in the game. The following (m) lines each describe one move. Each move is in one of the following formats:

• B x y: indicating that player B queries whether the diagonal connecting vertices \(x\) and \(y\) is in the triangulation.
• A ans: indicating that player A answers the query, where ans is either Y (yes) or N (no).

It is guaranteed that until the first non-optimal move (if any), A’s answers are consistent with a valid triangulation (i.e. a set of \(n-3\) non-intersecting diagonals).

outputFormat

For each game, output a single line. If the process remains optimal, output 0. Otherwise, output the first non-optimal move in the format A x or B x (where (x) is the move count of that player at the time the deviation occurs).

sample

3
5 4
B 1 3
A N
B 1 4
A Y
6 6
B 1 3
A N
B 1 4
A N
B 2 5
A Y
4 2
B 1 3
A Y

0
0
0

</p>