問題文
这个问题是讲座用问题。页面下方有解说。
N 考虑一个不一定简单的无向顶点图。 初始状态只有顶点,没有边,所有顶点都是孤立的。 下面 2 查询类型是 给予Q 次。
- 串联查询:顶点 A 和顶点 添加一条连接 B 的边。
- 决策查询:顶点
确定 A 和顶点
添加一条连接 B 是否是串联。如果是串联的话
Yes,否则No。
按顺序处理查询并输出判断查询的答案。 请注意,同一条边可能会添加多次,也可能会添加一条边本身。
连接意味着顶点 A 到顶点 这意味着可以通过沿着边缘到达 B 。 如果它们是相同的顶点,则定义要连接的 A 和 B 。 由于图是无向的,因此串联查询 当添加 A, B 之间的边时,A 它们的编号最大为 B 血 您还可以追踪到 B 它们的编号最大为 A 。
入力
输入将以以下格式从标准输入提供。
N Q P_1 A_1 B_1 P_2 A_2 B_2 : P_Q A_Q B_Q
- 1 行包含一个表示顶点数的整数。 N (1≦N≦100,000) 和一个表示查询数量的整数 表示第 Q (1 ≦ Q ≦ 200,000) 用空格分隔。
-
2 从线 Q 行数过多
关于第 i 第几行包含,i 个查询的类型的整数 P_i (0 ≦ P_i ≦ 1) 和一个表示要查询的顶点编号的整数 A_i, B_i (0 ≦ A_i, B_i ≦ N - 1) 用空格分隔。
- P_i = 0 指示该查询是链接查询。
- P_i = 1 表示该查询是判断查询。
出力
请输出每个判断查询。 在每个输出后添加换行符。
解説
入力例1
8 9 0 1 2 0 3 2 1 1 3 1 1 4 0 2 4 1 4 1 0 4 2 0 0 0 1 0 0
出力例1
Yes No Yes Yes
按以下步骤执行。
- 1 在第二个查询中,顶点 1 和顶点 连接 2 。 对
- 2 在第二个查询中,顶点 3 和顶点 连接 2 。 对
- 3 在第二个查询中,顶点 1 和顶点
连接 3 进行连接判断。既然已经连接了,
输出
Yes。 对 - 4 在第二个查询中,顶点 1 和顶点
连接 4 进行连接判断。由于没有连接,
对
No。 对 - 5 在第二个查询中,顶点 2 和顶点 连接 4 。 对
- 6 在第二个查询中,顶点 4 和顶点
连接 1 进行连接判断。它是连接的,
连接
Yes。 对 - 7 在第二个查询中,顶点 4 和顶点 连接 2 。这些已经连接,但可能会创建多个边。 连接
- 8 在第二个查询中,顶点 0 和顶点 连接 0 。尽管这些是相同的顶点,但它们也可以形成自环。 对
- 9 在第二个查询中,顶点 0 和顶点
连接 0 进行连接判断。由于相同的顶点总是可以被认为是相连的,
Yes。 对