E - Min and Max at the edge Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 1000 点

問題文

各頂点に番号が付いた無向グラフのうち、以下の条件を満たす全域木 T が取れるグラフを良いグラフといいます。なお、 2 頂点 u,v\ (u < v) を結ぶ辺を辺 (u,v) と表記します。

  • グラフのすべての辺 (u,v)\ (u < v) に対し、 T 上で頂点 u,v を結ぶただ 1 つの単純パスについて、単純パス上の頂点の番号の最小値、最大値はそれぞれ u,v である。

1 から N までの番号が付いた N 頂点からなる単純連結無向グラフ G があります。グラフ G には辺が M 本あり、 i 番目の辺は頂点 A_i,B_i\ (A_i < B_i) を結びます。

各 i=1,2,\dots,M に対し、 G から i 番目の辺を取り除いて得られるグラフが良いグラフであるか判定してください。

制約

  • 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 行目には 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

出力例 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

Score : 1000 points

Problem Statement

An undirected graph with numbered vertices is called a good graph if it has a spanning tree T that satisfies the following condition. Here, an edge connecting two vertices u and v (u < v) is denoted as edge (u,v).

  • For every edge (u,v) (u < v) in the graph, the minimum and maximum vertex numbers on the unique simple path connecting vertices u and v in T are u and v, respectively.

You are given a simple connected undirected graph G with N vertices numbered from 1 to N. The graph G has M edges, and the i-th edge connects vertices A_i and B_i (A_i < B_i).

For each i=1,2,\dots,M, determine whether the graph obtained by removing the i-th edge from G is a good graph.

Constraints

  • 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
  • All input values are integers.
  • The given graph is a simple connected undirected graph.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print M lines. The i-th line should contain Yes if the graph obtained by removing the i-th edge from G is a good graph, and No otherwise.

Sample Input 1

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

Sample Output 1

No
No
No
No
Yes
No
No
Yes
Yes

Consider the case where edge (4,6) is removed. A spanning tree formed by edges (1,3),(2,5),(3,4),(3,5),(5,6) satisfies the condition. For example, for edge (3,6), the simple path connecting vertices 3 and 6 traverses vertices 3,5,6 in this order, and the minimum and maximum vertex numbers on the path are 3 and 6, respectively, thus satisfying the condition. By verifying the other edges similarly, it can be seen that this spanning tree satisfies the condition, so the answer is Yes.

On the other hand, consider the case where edge (1,5) is removed. The same spanning tree does not satisfy the condition. For edge (4,6), the simple path connecting vertices 4 and 6 traverses vertices 4,3,5,6 in this order, and the minimum and maximum vertex numbers on the path are 3 and 6, respectively, thus not satisfying the condition. It can also be shown that no other spanning tree satisfies the condition, so the answer is No.

Sample Input 2

5 4
1 2
2 3
3 4
4 5

Sample Output 2

No
No
No
No

Removing an edge may disconnect the graph.

Sample Input 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

Sample Output 3

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