[AdditionalFile121.zip](file://AdditionalFile121.zip?type=additional_file)

#121. 「离线可过」动态图连通性

题目描述

这是一道被离线爆**的模板题。

你要维护一张无向简单图。你被要求加入删除一条边及查询两个点是否连通。

• 0：加入一条边。保证它不存在。
• 1：删除一条边。保证它存在。
• 2：查询两个点是否连通。

输入格式

输入的第一行是两个数 $N$ $M$。$N \le 5000, M \le 500000$。

接下来 $M$ 行，每一行三个数 $op, x, y$。$op$ 表示操作编号。

输出格式

对于每一个 $op = 2$ 的询问，输出一行 Y 或 N，表示两个节点是否连通。

样例 1

输入

200 5
2 123 127
0 123 127
2 123 127
1 127 123
2 123 127

输出

N
Y
N

样例 2

输入

4 10
0 1 2
0 2 3
0 3 1
2 1 4
0 4 3
2 1 4
1 2 3
2 1 4
1 1 3
2 1 4

输出

N
Y
Y
N

数据范围与提示

对于数据点 1，$N \le 200, M \le 200$。 对于数据点 2，$N = 5, M \le 30$。 对于数据点 3，$N = 10, M \le 1000$，其中查询的次数 $\ge 900$ 次。 对于数据点 4，$N = 300, M \le 50000$。 对于数据点 5，$N = 5000, M \le 200000$，没有操作 1，其中约 70% 是操作 2。 对于数据点 6，$N = 5000, M \le 200000$，没有操作 1，其中约 70% 是操作 0。 对于数据点 7、8，$N = 100, M \le 500000$。 对于数据点 9，$N = 5000, M \le 500000$，图是一棵树，其直径 $\le 6$。 对于数据点 10，$N = 5000, M \le 500000$，图是一棵树，其每个点度数 $\le 4$。

P.S. 其实 9 是菊花，10 是单链，而没有放随机树的点...