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

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

题目描述

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

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

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

输入格式

输入的第一行是两个数 N MN\ MN5000,M500000N \leq 5000,M \leq 500000

接下来 MM 行,每一行三个数 op,x,y\mathit{op}, x, yop\mathit{op} 表示操作编号。

输出格式

对于每一个 op=2\mathit{op}=2 的询问,输出一行 YN ,表示两个节点是否连通。

样例 1

200 5
2 123 127
0 123 127
2 123 127
1 127 123
2 123 127
N
Y
N
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,N200,M200N \leq 200,M \leq 200
对于数据点 2,N=5,M30N=5,M \leq 30
对于数据点 3,N=10,M1000N=10,M \leq 1000,其中查询的次数 900\geq 900 次。
对于数据点 4,N=300,M50000N=300,M \leq 50000
对于数据点 5,N=5000,M200000N=5000,M \leq 200000,没有操作 1,其中约 70%70 \% 是操作 2。
对于数据点 6,N=5000,M200000N=5000,M \leq 200000,没有操作 1,其中约 70%70 \% 是操作 0。
对于数据点 7、8,N=100,M500000N=100,M \leq 500000
对于数据点 9,N=5000,M500000N=5000,M \leq 500000,图是一棵树,其直径 6 \leq 6
对于数据点 10, N=5000,M500000N=5000,M \leq 500000,图是一棵树,其每个点度数 4 \leq 4

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