P3367 【Template】Disjoint Set Union

**The constraints for this problem have been updated to $1 \le N \le 2 \times 10^5$, $1 \le M \le 10^6$.**

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

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`.

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

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