题目描述

对于一个编号的无向图，如果存在一棵满足以下条件的生成树 $T$，则称该图为好图。对于 $2$ 个顶点 $u,v\ (u < v)$ 之间的边，记为边 $(u,v)$。

• 对于图中的每一条边 $(u,v)\ (u < v)$，在 $T$ 上连接顶点 $u,v$ 的唯一简单路径上，路径经过的所有顶点编号的最小值和最大值分别为 $u,v$。

给定一个包含 $N$ 个顶点、顶点编号为 $1$ 到 $N$ 的简单连通无向图 $G$。图 $G$ 有 $M$ 条边，第 $i$ 条边连接顶点 $A_i,B_i\ (A_i < B_i)$。

对于每个 $i=1,2,\dots,M$，请判断从 $G$ 中删除第 $i$ 条边后得到的图是否为好图。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$

输出格式

输出 $M$ 行。第 $i$ 行若从 $G$ 中删除第 $i$ 条边后得到的图为好图，则输出 Yes，否则输出 No。

样例 1

输入

6 9
1 3
1 5
2 5
2 6
3 4
3 5
3 6
4 6
5 6

输出

No
No
No
No
Yes
No
No
Yes
Yes

样例 2

输入

5 4
1 2
2 3
3 4
4 5

输出

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

输出

No
No
No
Yes
Yes
No
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No

说明/提示

限制条件

• $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$
• 输入的所有值均为整数
• 给定的图为简单连通无向图

样例解释 1

以删除边 $(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

删除某条边后，图也有可能变为非连通图。

由 ChatGPT 4.1 翻译