#P3031. 【模板】并查集

【模板】并查集

题目描述

如题,现在有一个并查集,你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,MN,M ,表示共有 NN 个元素和 MM 个操作。

接下来 MM 行,每行包含三个整数 Zi,Xi,YiZ_i,X_i,Y_i

Zi=1Z_i=1 时,将 XiX_iYiY_i 所在的集合合并。

Zi=2Z_i=2 时,输出 XiX_iYiY_i 是否在同一集合内,是的输出 Y ;否则输出 N

输出格式

对于每一个 Zi=2Z_i=2 的操作,都有一行输出,每行包含一个大写字母,为 Y 或者 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

提示

对于 30%30\% 的数据,N10N \le 10M20M \le 20

对于 70%70\% 的数据,N100N \le 100M103M \le 10^3

对于 100%100\% 的数据,1N1041\le N \le 10^41M2×1051\le M \le 2\times 10^51Xi,YiN1 \le X_i, Y_i \le NZi{1,2}Z_i \in \{ 1, 2 \}