题目描述

本题题解已发表至 讨论区

某国有n个城市，编号为1到n，这些城市之间计划修建若干条道路，每条道路连接两个城市。你的任务是帮助该国政府处理以下两类操作：

1. 连接两个城市：在两个城市之间修建一条道路。如果两个城市已经通过某些道路间接连通，则无需重复修建。
2. 判断连通性：询问两个城市是否已经直接或间接连通。

输入描述

第一行包含两个整数 n 和 q，分别表示城市的数量和操作的数量。

接下来的 q 行中，每行描述一个操作，有以下两种格式：

• 1 a b表示在城市 a和城市 b之间修建一条道路。
• 2 a b表示询问城市 a和城市 b是否连通。

输出描述

对于每个操作类型为2的询问，输出Y或N，连通输出 Y ；否则输出 N。

示例 1

输入

5 5
1 1 2
1 2 3
2 1 3
2 1 4
1 4 5

输出

Y
N

备注

对于 $30\%$ 的数据，$N \le 10$，$M \le 20$。
对于 $70\%$ 的数据，$N \le 100$，$M \le 10^3$。
对于 $100\%$ 的数据，$1\le N \le 10^4$，$1\le M \le 2\times 10^5$，$1 \le X_i, Y_i \le N$，$Z_i \in \{ 1, 2 \}$。