ヒント：https://atcoder.jp/contests/arc211/editorial/14503

---

結論を先に述べます。以下のアルゴリズムが正当です。

• 頂点 \(1\) からDFS木をとる（DFS木についてはABC251-Fの公式解説を参照）。その後、各頂点について頂点 \(1\) の方に青色の道標を立てる。
• 使えない有向辺を取り除いて、頂点 \(2\) からすべての頂点にたどり着けないなら No 。そうでないなら Yes で、適当な木を取って、各頂点について頂点 \(2\) の方に黄色の道標を立てる。

このアルゴリズムが正当であることの証明は最後にして、「なぜwriterがこのアルゴリズムを思いついたのか？」に焦点を当てて解説します。人によって思いつき方には差があるかもしれませんが、参考までに。

Part1. No になる場合とは？

ある辺を除いたとき、連結成分が分かれたとします。このとき、頂点 \(1\) と頂点 \(2\) が同じ側にあるとき、目標を達成することは不可能です。頂点 \(1,2\) がない側から移るときにその辺を通る必要がありますが、その辺に道標を \(2\) つとも立てることはできないからです。

Part2. 橋のない場合に帰着する

辺を除いたときに連結成分が分かれる辺を、グラフ理論の用語で橋といいます。

先ほどわかりやすく No となるケースを弾いたので、橋を取り除くと、頂点 \(1\) と頂点 \(2\) は異なる連結成分に属します。よって、橋の両端に立てる道標の立て方が決まります。橋を取り除いてしまうと、同じ問題を \(2\) つの連結成分について解くことになります！

ということで、これを繰り返すことで橋のない場合に帰着することができました（ただし、目指すべき頂点が同じになることがあります。それでも特に問題ないことは最後の証明パートで示すことにします）。

Part3. 橋のない場合では？

まず重要な事実を提示します。青色の道標の立て方をすべて決めてしまいます。すると、頂点 \(2\) から青色の道標を利用せずにすべての頂点までたどり着ければ、適当に黄色の道標を立てれば条件を満たす立て方が構成できます。うまく青色の道標を立てましょう。

達成しにくい状況…つまり辺ができる限り少ない状況、を考えます。わかりやすいのではサイクルですが、これは明らかに達成可能です。頂点 \(1\) の隣から遠回りしてぐるっと \(1\) 回転するように青色の道標を配置し、黄色の道標はそれと逆向きにぐるっと回せばよいです。

これを機械的に構築しようとすると、「頂点 \(1\) からDFSをすると良いのではないか？」と思いつきます。他のグラフでも試してみても、うまくいきそうです。実際「DFS木をとったとき、余った辺はすべて後退辺である」ことと、先程橋を取り除いたことを利用して証明できる（この証明は後述します）ので、予想が確信に変わります。

Part4. 一般の場合は？

橋がある場合でも、DFS木をとるのが結局正当なことが容易に確認できます。No である場合を最初に弾かなくとも、うまく道標を立てられなければ No を出力すればよいです。

---

最後に、アルゴリズムが正当なことの証明です。先程の通り、橋のない場合に正当なことを証明すればよいです。（その代わり、目指す頂点が同じ頂点の場合も正当なことを証明しないといけません。が、これは可能です。）

青色の道標を頂点 \(1\) を根とするDFS木状（ただし、道標は頂点 \(1\) 向き）に立てましたから、「道標に逆らって移動する（＝子に移動する）」「後対辺を移動する」のどちらかを繰り返してすべての頂点同士で行き来できればよいです。さらに、頂点 \(1\) からは前者のみですべての頂点にたどり着けますから、どの頂点からも頂点 \(1\) にたどり着ければよいです。

これはさらに、「頂点 \(1\) 以外のある頂点にいるとき、その祖先の頂点に移動できる」ことを証明すればよいです。それができれば、繰り返し行うことでいずれ頂点 \(1\) にたどり着くことができます。

今いる頂点から、その親を指す辺を考えます。その辺は橋ではありませんでしたから、その祖先と子孫を結ぶ後退辺が \(1\) つは存在するはずです。その後退辺に沿って移動することで、祖先に移動することができます。よって証明できました。

実装例 (Python (Codon 0.19.3), 296ms)

import sys

def bdfs(pos):
    for i in gr[pos]:
        if bpar[i] == -1 and i != 0:
            bpar[i] = pos
            bdfs(i)

def ydfs(pos):
    for i in gr[pos]:
        if ypar[i] == -1 and i != 1 and bpar[i] != pos:
            ypar[i] = pos
            ydfs(i)

N, M = [int(i) for i in input().split()]

gr = [[] for i in range(N)]

for i in range(M):
    U, V = [int(i) for i in input().split()]
    U -= 1
    V -= 1
    gr[U].append(V)
    gr[V].append(U)

bpar = [-1] * N
ypar = [-1] * N

bdfs(0)
ydfs(1)

ans = "Yes"

for i in range(N):
    if i != 1 and ypar[i] == -1:
        print("No")
        sys.exit()

print("Yes")

print(ypar[0] + 1)
print(bpar[1] + 1)
for i in range(2, N):
    print(bpar[i] + 1, ypar[i] + 1)