Description

As stated, there is a disjoint set union (union-find). You need to perform union and query operations.

Input Format

The first line contains two integers $N, M$, representing $N$ elements and $M$ operations.

The next $M$ lines each contain three integers $Z_i, X_i, Y_i$.

When $Z_i = 1$, union the sets containing $X_i$ and $Y_i$.

When $Z_i = 2$, output whether $X_i$ and $Y_i$ are in the same set. Output Y if yes; otherwise output N.

Output Format

For each operation with $Z_i = 2$, output one line containing a single uppercase letter, either Y or N.

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

N
Y
N
Y

Hint

For $15\%$ of the testdata, $N \le 10$, $M \le 20$.

For $35\%$ of the testdata, $N \le 100$, $M \le 10^3$.

For $50\%$ of the testdata, $1 \le N \le 10^4$, $1 \le M \le 2 \times 10^5$.

For $100\%$ of the testdata, $1 \le N \le 2 \times 10^5$, $1 \le M \le 10^6$, $1 \le X_i, Y_i \le N$, $Z_i \in \{ 1, 2 \}$.

Translated by ChatGPT 5