D - Michishirube Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

N 頂点 M 辺の単純連結無向グラフが与えられます。i 番目 (1\leq i\leq M) の辺は頂点 U_i と頂点 V_i を結ぶ無向辺です。

すべての頂点に、以下のように道標を立てます。

  • 頂点 1 以外のすべての頂点に、隣接している頂点のうちどれか 1 つを指す青色の道標を立てる。
  • 頂点 2 以外のすべての頂点に、隣接している頂点のうちどれか 1 つを指す黄色の道標を立てる。

ただし、同じ頂点にある 2 つの道標が同じ頂点を指してはいけません。

以下の条件を満たすように道標を立てることは可能か判定し、可能なら道標の立て方を 1 つ出力してください。

  • 頂点 1 以外のどの頂点からも、青色の道標の指す頂点に動くことを有限回繰り返すことで頂点 1 に到達することができる。
  • 頂点 2 以外のどの頂点からも、黄色の道標の指す頂点に動くことを有限回繰り返すことで頂点 2 に到達することができる。

条件を満たす道標の立て方が複数ある場合、どれを出力してもかまいません。

制約

  • 2\leq N\leq 2\times 10^5
  • 1\leq M\leq 3\times 10^5
  • 1\leq U_i\lt V_i\leq N (1\leq i\leq M)
  • 与えられるグラフは単純かつ連結
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M

出力

条件を満たす道標の立て方が存在しない場合、No とだけ出力せよ。

存在する場合、N+1 行出力せよ。

1 行目には、Yes と出力せよ。

2 行目には、頂点 1 に立てる黄色の道標が指す頂点の番号を出力せよ。

3 行目には、頂点 2 に立てる青色の道標が指す頂点の番号を出力せよ。

i 行目 (4\leq i\leq N+1) には、頂点 i-1 に立てる青色の道標が指す頂点の番号、黄色の道標が指す頂点の番号をこの順に空白区切りで出力せよ。

解が複数ある場合、どれを出力してもかまわない。

入力例 1

7 8
1 3
3 4
4 5
1 5
4 6
2 6
2 7
4 7

出力例 1

Yes
5
6
4 1
5 6
1 4
4 2
4 2

下図のような道標の立て方です。たとえば、頂点 3 からは

  • 青色の道標に沿うと、頂点 3\rightarrow 4\rightarrow 5\rightarrow 1 と動き、最終的に頂点 1 に到達します。
  • 黄色の道標に沿うと、頂点 3\rightarrow 1\rightarrow 5\rightarrow 4 \rightarrow 6\rightarrow 2 と動き、最終的に頂点 2 に到達します。

また、頂点 2 から青色の道標に沿って移動すると頂点 1 に到達できること、頂点 1 から黄色の道標に沿って移動すると頂点 2 に到達できることも確かめることができます。その他の頂点も条件を満たします。

この他にも複数の解がありますが、頂点 3 にある青色の道標と黄色の道標をともに頂点 4 に向けてはいけません。同じ頂点にある道標が同じ頂点を指してしまうためです。

入力例 2

10 12
1 3
3 4
4 5
1 5
4 6
2 6
2 7
4 7
4 8
8 9
9 10
8 10

出力例 2

No

条件を満たす道標の立て方は存在しません。

Score : 700 points

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. The i-th edge (1\leq i\leq M) is an undirected edge connecting vertices U_i and V_i.

Place signposts at all vertices as follows:

  • At every vertex except vertex 1, place a blue signpost pointing to one of its adjacent vertices.
  • At every vertex except vertex 2, place a yellow signpost pointing to one of its adjacent vertices.

Here, the two signposts at the same vertex must not point to the same vertex.

Determine whether it is possible to place signposts satisfying the following conditions, and if possible, output one way to place them:

  • From any vertex other than vertex 1, you can reach vertex 1 by repeatedly moving to the vertex pointed to by the blue signpost a finite number of times.
  • From any vertex other than vertex 2, you can reach vertex 2 by repeatedly moving to the vertex pointed to by the yellow signpost a finite number of times.

If there are multiple ways to place signposts satisfying the conditions, you may output any of them.

Constraints

  • 2\leq N\leq 2\times 10^5
  • 1\leq M\leq 3\times 10^5
  • 1\leq U_i\lt V_i\leq N (1\leq i\leq M)
  • The given graph is simple and connected.
  • All input values are integers.

Input

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

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M

Output

If there is no way to place signposts satisfying the conditions, output No only.

If there is, output N+1 lines.

The first line should contain Yes.

The second line should contain the number of the vertex pointed to by the yellow signpost at vertex 1.

The third line should contain the number of the vertex pointed to by the blue signpost at vertex 2.

The i-th line (4\leq i\leq N+1) should contain the number of the vertex pointed to by the blue signpost at vertex i-1 and the number of the vertex pointed to by the yellow signpost at vertex i-1, in this order, separated by a space.

If there are multiple solutions, you may output any of them.

Sample Input 1

7 8
1 3
3 4
4 5
1 5
4 6
2 6
2 7
4 7

Sample Output 1

Yes
5
6
4 1
5 6
1 4
4 2
4 2

Here, signposts are placed as shown in the figure below. For example, from vertex 3:

  • Following the blue signpost, you move as vertex 3\rightarrow 4\rightarrow 5\rightarrow 1, eventually reaching vertex 1.
  • Following the yellow signpost, you move as vertex 3\rightarrow 1\rightarrow 5\rightarrow 4 \rightarrow 6\rightarrow 2, eventually reaching vertex 2.

You can also verify that following the blue signpost from vertex 2 leads to vertex 1, and following the yellow signpost from vertex 1 leads to vertex 2. The other vertices also satisfy the conditions.

There are multiple other solutions, but you must not have both the blue signpost and the yellow signpost at vertex 3 point to vertex 4, because the signposts at the same vertex would point to the same vertex.

Sample Input 2

10 12
1 3
3 4
4 5
1 5
4 6
2 6
2 7
4 7
4 8
8 9
9 10
8 10

Sample Output 2

No

There is no way to place signposts satisfying the conditions.