Treasure Hunt Game

The graph has $N$ vertices numbered 1 to $N$ and $M$ undirected edges. Every vertex is connected to at least one edge. Some vertices belong to Alice, and the rest belong to Bob. Some vertices contain a treasure.

Alice and Bob place a token on a vertex of the graph and play a game. At the start of each turn, if the token is on one of Alice's vertices, Alice must choose one edge adjacent to the current vertex and move the token to its other endpoint. Bob does the same on his vertices. The token cannot stay where it is.

When the token visits a vertex with a treasure, the player gets one treasure. If that vertex was visited before, the player gets another treasure each time the token returns to it.

Alice wants the token to visit treasure vertices infinitely often, and Bob wants to prevent this. Precisely, play the game for $10^{100}$ turns. If the token is on a treasure vertex in at least $10^{90}$ of those turns, Alice wins. Otherwise, Bob wins.

Assuming both players always play optimally, determine who wins for each starting vertex.

The first line contains the number of test cases $T$. ($1 \le T \le 50$)

The first line of each test case contains integers $N$ and $M$. ($1 \le N \le 100\,000$, $1 \le M \le 200\,000$)

The next line contains a string of length $N$. Each character is A or B. If the $i$-th character is A, vertex $i$ belongs to Alice. If it is B, vertex $i$ belongs to Bob.

The next line contains a string of length $N$. Each character is T or .. If the $i$-th character is T, vertex $i$ has a treasure. If it is ., vertex $i$ has no treasure.

The next $M$ lines each contain two integers $u_i$ and $v_i$, separated by a space, the endpoints of the $i$-th edge. ($1 \le u_i, v_i \le N$, $u_i \neq v_i$) No two edges connect the same pair of vertices.

In all test cases, the sum of $N$ and the sum of $M$ each do not exceed 2,000,000.

For each test case, print a line "Case #$C$", where $C$ is the test case number. On the next line, print a string of length $N$ made of A or B. The $i$-th character is A if Alice wins when the game starts with the token on vertex $i$, and B if Bob wins.