AT_arc181_e.[ARC181E] Min and Max at the edge

对于一个编号的无向图，如果存在一棵满足以下条件的生成树 $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。

限制条件

• $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 翻译