400971: GYM100298 D Great Hunt

B. Demonstrationstime limit per test12.0 smemory limit per test256 megabytesinputstandard inputoutputstandard output

Lord Michael is having a hard time – the continuous increase of tax rates has led the people of Valeostan to rebel against his tyranny. A great number of citizens formed a demonstration which marches along Valeostan's streets. Up to one street can be occupied by the demonstration at any time.

To appease the people, Michael decided to improve Valeostan's infrastructure, and build a number of roads in the country. As a royal engineer, your task is to process two types of queries:

• x y - order to build a bidirectional road between cites x and y (1 ≤ x ≠ y ≤ n),
• x y - check if the connection between cites x and y is safe (1 ≤ x, y ≤ n).

The connection between two cites is safe if one can get from one city to another regardless of whether some road is occupied by the demonstration.Input

The first line of input consists of a single integer – the number of test cases.

The first line of every test case contains two integers: n - the number of cites (1 ≤ n ≤ 100000, and q - the number of queries (1 ≤ q ≤ 700000). Next q lines contain queries in the format described above, one per line.

Output

For every query output a single line - 'NO' if safe connection between two cities provided in the query doesn't exist. 'SI' otherwise.

ExamplesInput

1
8 14
BUILD 1 2
BUILD 1 3
CHECK 1 3
BUILD 2 3
CHECK 1 3
BUILD 4 5
BUILD 4 6
BUILD 5 6
BUILD 1 4
CHECK 2 5
BUILD 3 6
CHECK 2 5
BUILD 7 8
CHECK 7 8

Output

NO
SI
NO
SI
NO