In the distant land of yore, there lived a weeb king. As a weeb king, he valued anime above all else including roads. And so it came to be that, when it came time to go to the anime conventions, he realised his folly: **there were no roads in his kingdom, whatsoever**! Angered, he went to his chief adviser (you) and asked them to simulate actions:

`A x y`

: Build a road between cities and .`Q x y`

: Check if cities and are connected by the roads.

Since you want to please the king (maybe he'll get you something nice from the next convention in return!), you'll have to answer his queries.

#### Input Specification

The first line will have two integers, , and , the number of cities and queries, respectively.

The next lines each have a query. It is guaranteed that .

For of points, .

#### Output Specification

For each query in the form `Q x y`

, print `Y`

if you can travel from city to city . Otherwise, print `N`

.

#### Sample Input

```
5 6
A 1 2
A 2 3
Q 1 3
A 1 5
Q 5 2
Q 4 1
```

#### Sample Output

```
Y
Y
N
```

#### Explanation

For the first query, the king can travel along the following path:

For the second query, the king can travel along the following path:

For the third query, there are no roads that connect to city 4.

## Comments

Since the original data were weak, the data were replaced with cases for each subtask.

can somebody give some pointers for my code

https://xkcd.com/138/

bruh

for each Q, add new edge if x and y is connected

Any optimization tips for my program?

Doing BFS for every query is not required. There is a data structure that can solve these queries in sub logarithmic time.

is it the disjoint set thingy?