Hints: https://atcoder.jp/contests/arc211/editorial/14696

---

Let me state the conclusion first. The following algorithm is correct:

• Take a DFS tree from vertex \(1\) (for DFS trees, see the official editorial of ABC251-F). Then, for each vertex, place a blue signpost toward vertex \(1\).
• Remove unusable directed edges, and if not all vertices can be reached from vertex \(2\), output No. Otherwise, output Yes, take an appropriate tree, and for each vertex, place a yellow signpost toward vertex \(2\).

I’ll leave the proof that this algorithm is correct until the end, and focus on “why did the writer come up with this algorithm?” The way of coming up with it may vary by person, but I hope it helps.

Part 1. When does it become No?

Suppose that when a certain edge is removed, the connected components split. At this time, if vertices \(1\) and \(2\) are on the same side, it is impossible to achieve the goal. This is because when moving from the side without vertices \(1\) and \(2\), you need to pass through that edge, but you cannot place both signposts on that edge.

Part 2. Reduce to the case without bridges

An edge whose removal splits the connected components is called a bridge in graph theory terminology.

Since we have eliminated the easily seen No case, when we remove bridges, vertices \(1\) and \(2\) belong to different connected components. Therefore, the way to place signposts at both ends of bridges is determined. If we remove bridges, we solve the same problem for two connected components!

So, by repeating this, we can reduce to the case without bridges (though the target vertices may become the same. It will be shown in the final proof part that this is not really a problem).

Part 3. What about the case without bridges?

First, let me present an important fact. Let us completely fix how to place the blue signposts. Then, if all vertices can be reached from vertex \(2\) without using blue signposts, we can construct a way to place signposts satisfying the conditions by placing yellow signposts appropriately. Let’s place the blue signposts well.

Consider a situation where the objective is hard to achieve… that is, a situation with as few edges as possible. An easy example is a cycle, but this is clearly achievable. Place blue signposts from the neighbor of vertex \(1\) to go around once the long way, and yellow signposts can go around in the opposite direction.

When trying to construct this mechanically, you might think, “Wouldn’t it be good to do DFS from vertex \(1\)?” Trying other graphs as well, it seems to work well. In fact, it can be proved (this proof will be given later) using “when taking a DFS tree, all remaining edges are back edges” and the fact that we removed bridges earlier, so the guess becomes conviction.

Part 4. What about the general case?

Even when there are bridges, it is easy to verify that taking a DFS tree is ultimately correct. Even without eliminating No cases at the beginning, we can just output No if we cannot place signposts well.

---

Finally, here is the proof that the algorithm is correct. As mentioned earlier, we need only prove that it is correct in the case without bridges. (Instead, we must also prove that it is correct when the target vertex is the same vertex. But this is possible.)

Since we placed blue signposts in the form of a DFS tree rooted at vertex \(1\) (but with signposts pointing toward vertex \(1\)), it is sufficient if we can move between all vertices by repeating either “moving against the signpost (= moving to a child)” or “moving along a back edge”. Furthermore, since all vertices can be reached from vertex \(1\) using only the former, it is sufficient if vertex \(1\) can be reached from any vertex.

This can be further reduced to proving that “when at some vertex other than vertex \(1\), you can move to an ancestor vertex of that vertex”. If we can do that, we can eventually reach vertex \(1\) by repeating it.

Consider the edge from the current vertex pointing to its parent. Since that edge was not a bridge, there must be at least one back edge connecting that ancestor and descendant. By moving along that back edge, we can move to an ancestor. Thus, the proof is complete.

Implementation Example (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)