题目背景

本题采用扩展后的数据范围，$N$ 的上限为 $2\times10^5$，$M$ 的上限为 $10^6$。

题目描述

编号为 $1$ 至 $N$ 的元素初始各自属于一个集合。按给出的顺序完成两类操作：合并两个元素所属的集合，以及查询两个元素是否已经属于同一个集合。

输入格式

第一行给出元素个数 $N$ 和操作次数 $M$。接下来按执行顺序输入 $M$ 行操作，每行为三个整数 $Z_i,X_i,Y_i$。

• $Z_i=1$ 时，将包含 $X_i$ 的集合与包含 $Y_i$ 的集合合并。
• $Z_i=2$ 时，查询 $X_i$ 与 $Y_i$ 是否在同一个集合中。

输出格式

每次查询输出一行；属于同一集合时输出 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

说明/提示

原题的分档数据范围如下。