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 ~Q~ actions:
A x y: Build a road between cities ~x~ and ~y~.
Q x y: Check if cities ~x~ and ~y~ 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.
The first line will have two integers, ~N~, and ~Q\ (2 \le N \le 10^5; 1 \le Q \le 10 ^ 5)~, the number of cities and queries, respectively.
The next ~Q~ lines each have a query. It is guaranteed that ~x \neq y;1 \le x, y \le N~.
For ~30\%~ of points, ~1 \le N, Q \le 1\,000~.
For each query in the form
Q x y, print
Y if you can travel from city ~x~ to city ~y~. Otherwise, print
5 6 A 1 2 A 2 3 Q 1 3 A 1 5 Q 5 2 Q 4 1
Y Y N
For the first query, the king can travel along the following path: ~1 \rightarrow 2 \rightarrow 3~
For the second query, the king can travel along the following path: ~5 \rightarrow 1 \rightarrow 2~
For the third query, there are no roads that connect to city 4.