分数: 1000 点
问题陈述
具有编号顶点的无向图称为 好图 如果它有生成树 T 满足以下条件。这里,连接两个顶点的边 u 和 v (u < v) 表示为边缘 (u,v).
- 对于每条边 (u,v) (u < v) 图中,连接顶点的唯一简单路径上的最小和最大顶点数 u 和 v in T 是 u 和 v。
给你一个简单的连通无向图 G 与 N 顶点编号自 1 to N。图表 G 有 M 边缘,以及 i第一条边连接顶点 A_i 和 B_i (A_i < B_i).
对于每个 i=1,2,\dots,M,判断去除后得到的图是否为 i第一条边 G 是 好图.
约束
- 2 \leq N \leq 2 \times 10^5
- N-1 \leq M \leq 2 \times 10^5
- 1 \leq A_i < B_i \leq N
- 所有输入值均为整数。
- 给定的图是一个简单的连通无向图。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 \vdots A_M B_M
输出
打印 M 行。的 i- 第行应包含 Yes 如果通过删除得到的图 i第一条边 G 是 好图,和 No 否则。
样本输入 1
6 9 1 3 1 5 2 5 2 6 3 4 3 5 3 6 4 6 5 6
示例输出 1
No No No No Yes No No Yes Yes
考虑边缘的情况 (4,6) 已删除。由边组成的生成树 (1,3),(2,5),(3,4),(3,5),(5,6) 满足条件。例如,对于边缘 (3,6),连接顶点的简单路径 3 和 6 遍历顶点 3,5,6 按此顺序,路径上的最小和最大顶点数为 3 和 6,从而满足条件。类似地验证其他边,可以看出这棵生成树满足条件,所以答案是 Yes.
另一方面,考虑边缘的情况 (1,5) 已删除。同一生成树不满足条件。对于边缘 (4,6),连接顶点的简单路径 4 和 6 遍历顶点 4,3,5,6 按此顺序,路径上的最小和最大顶点数为 3 和 6,因此不满足条件。也可以证明没有其他生成树满足条件,所以答案是 No.
示例输入 2
5 4 1 2 2 3 3 4 4 5
示例输出 2
No No No No
删除边可能会断开图形的连接。
示例输入 3
15 20 12 13 7 8 5 7 8 10 9 12 4 5 11 12 2 4 6 8 4 14 1 2 14 15 2 9 3 8 2 15 10 11 13 14 8 9 7 14 5 13
示例输出 3
No No No Yes Yes No Yes No No No No No No No No Yes No No No No