Many Roads

The mighty river ByteStream runs through the fertile lands of ByteLands. The 2N cities of ByteLand are split by the river perfectly, N cities on one side, and N cities on the other. On the north side, cities are labeled 1 through N from west to east. Similarly, on the south side of the river, cities are labeled N+1 through 2N from west to east. Let’s consider the following image:

The arrows indicate unidirectional roads from one city to another. On the north side (top), there is a one-way road from each city to its nearest one to the east (right), except the Nth city. On the south side (bottom), there is a one-way road from each city to its nearest one to the west (left) except the (N+1)th city.

As you can easily predict, this is a very bad design for a road network and prone to congestion. Roads often get blocked entirely. But, fear not, the ByteLandians have mastered the art of DuctTape solutions. In order to solve congestion problems, they have decided to add bridges that connect two cities from the opposite banks of the river.

However, to keep the expenditure at a minimum, all the bridges are bidirectional, and no two bridges will ever intersect. No two bridges will start or end from the same city either. Thus, each town will be directly connected by a bridge to at most one town on the other side of the river. Let’s take a look at the following picture to understand the scenario:

Note, the empty roads between (3, 4), (6-7), and (13-12) indicate that these roads have been blocked completely. As we can see, three bidirectional bridges have been constructed between the cities (2, 11), (5, 12), and (6,16).

However, this also complicates the routing between two cities. So, you will have to write a program to answer some queries. You will have to process M requests chronologically. The requests will be one of the following 3 forms:

1. A u v - a bidirectional bridge has been added between cities u and v

2. B u v - a unidirectional road between cities u and v has blocked

3. Q u v - query whether it is possible to reach city v from u.

At the very beginning, all roads are open and no bridge has been built.

Input

The first line of the input file contains T (T <= 20), the number of test cases.

Each test case starts with two integers N (1 <= N <= 10^9) and M (1 <= M <= 2*10^5) denoting the number of cities on each bank and queries respectively. The following M lines contain the description of chronological requests described above. Here, 1 <= u, v <= 2*N.

Output

For each test case, first print the serial number of the test case in a line, followed by a line for each of the ‘Q’ type requests containing “Yes” or “No” depending on whether it is possible to reach city v from city u or not. Please check the sample input-output section for formatting details.

Sample

2
5 6
A 4 9
Q 1 7
B 3 2
Q 1 7
A 1 8
Q 1 7
6 10
A 3 7
A 4 10
Q 1 11
A 12 5
Q 2 11
B 10 11
Q 2 10
Q 9 6
B 1 2
Q 1 2

Case 1:
Yes
No
Yes
Case 2:
No
Yes
Yes
Yes
No

The input file is very large, please use faster IO.