← 返回题目列表

AtCoder · arc181_e

E. 边缘的最小值和最大值

中文机器翻译题面 查看原题

分数: 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