Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

There is a cave. The cave has N rooms and M passages. The rooms are numbered 1 to N, and…

  1. User

    There is a cave.

    The cave has N rooms and M passages. The rooms are numbered 1 to N, and the passages are numbered 1 to M. Passage i connects Room A_i and Room B_i bidirectionally. One can travel between any two rooms by traversing passages. Room 1 is a special room with an entrance from the outside.

    It is dark in the cave, so we have decided to place a signpost in each room except Room 1. The signpost in each room will point to one of the rooms directly connected to that room with a passage.

    Since it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room 1.

    • If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible.

    Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists.

    Constraints

    • All values in input are integers.
    • 2 \leq N \leq 10^5
    • 1 \leq M \leq 2 \times 10^5
    • 1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)
    • A_i \neq B_i\ (1 \leq i \leq M)
    • One can travel between any two rooms by traversing passages.

    Input

    Input is given from Standard Input in the following format:

    N M A_1 B_1 : A_M B_M

    Output

    If there is no way to place signposts satisfying the objective, print No.

    Otherwise, print N lines. The first line should contain Yes, and the i-th line (2 \leq i \leq N) should contain the integer representing the room indicated by the signpost in Room i.

    Examples

    Input

    4 4 1 2 2 3 3 4 4 2

    Output

    Yes 1 2 2

    Input

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

    Output

    Yes 6 5 5 1 1

  2. DeepSeek Assistant

    We need to solve a graph problem: Given an undirected connected graph with N nodes, node 1 is special. We need to assign a direction (choose one neighbor) for each node v (v != 1) as signpost, such that for each v (v != 1), if you start at v and follow the signposts repeatedly, you reach node 1 using the minimum possible number of steps (i.e., the distance from v to 1 in the original graph). In other words, the signpost should point to a neighbor that lies on a shortest path from v to 1. That is, if we consider the shortest path tree (BFS tree) from node 1, then each node (except 1) should point to a parent in some shortest path tree. However, note that the graph may have multiple shortest paths (i.e., nodes may have multiple neighbors that are at distance d-1). So we need to pick for each node (v != 1) a neighbor u such that dist(1,u) = dist(1,v) - 1. That ensures that following signposts yields a path of length dist(v,1) that is monotonic decreasing distance and minimal. But we also need that the signposts produce a path that eventually reaches 1. If each node points to a neighbor with smaller distance, then repeatedly following signposts will strictly decrease distance until reaching 1, because distance is finite and nonnegative integer that strictly decreases each step. So we just need to assign each node (except 1) to one of its neighbors that is closer to 1 (i.e., with distance = dist(v)-1). That is necessary and sufficient.

    Thus the problem reduces to: Compute distances from node 1 (BFS). Then for each node v (2..N), check if there exists a neighbor u such that dist[u] = dist[v] - 1. If for any node v there is no such neighbor, then answer is No. Otherwise, for each v, output any such neighbor u. That yields a valid assignment.

    But is there any subtlety? The condition: "If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible." Means that the path taken (by following signposts) is a shortest path from that node to 1. That requires that each step moves to a neighbor that is on some shortest path, and the sequence must be such that each step reduces distance by exactly 1. So indeed we need that for each node v, the chosen neighbor u satisfies dist(u) = dist(v) - 1. Additionally, following the signposts from u must also continue along a shortest path; but if we assign all nodes that way, then from u we will point to some w with dist(w)=dist(u)-1, etc. So it's consistent. So the condition reduces exactly to having each node point to a neighbor with distance one less.

    Thus algorithm: BFS from node 1 to compute distances (unweighted graph). Then for each node v from 2 to N, iterate its neighbors to find any neighbor with distance = dist[v]-1. If none, print No. Otherwise, pick the first found (or any) and record it. Print Yes and then for i=2..N print the chosen neighbor.

    Constraints: N up to 1e5, M up to 2e5. BFS O(N+M) using adjacency list. Fine.

    But wait: The graph may have multiple edges? Input says A_i != B_i, but could there be duplicate edges? Probably allowed but not harmful. We'll store adjacency.

    Edge Cases: Node 1 distance = 0. For node 1 we don't assign a signpost. For neighbor nodes at distance 1, they must point to node 1 (since only neighbor with distance 0). That's okay.

    Now confirm examples:

    Example1: 4 4 1-2 2-3 3-4 4-2

    Compute distances from 1: dist1=0, dist2=1 (1-2), dist3: from 2 distance 2, also from 4? Actually graph: 1-2,2-3,3-4,4-2. So distances: 1:0, 2:1, 3: from 2:2, 4: from 2:2? 2-4 edge: distance 2. So dist3=2, dist4=2. Now for node 2 (dist1) neighbor: 1 with dist0, so choose 1. Node 3 (dist2) neighbors: 2 (dist1) and 4 (dist2). So must pick 2. Node 4 (dist2) neighbors: 3(dist2),2(dist1) -> pick 2. Output: Yes, then for 2:1, 3:2, 4:2 matches.

    Example2: 6 9 Edges: 3-4,6-1,2-4,5-3,4-6,1-5,6-2,4-5,5-6 Let's compute distances from 1. Adj: 1:6,5. So dist1=0. Neighbors: 6,5 => dist6=1, dist5=1. Next from 6: neighbors:1,4,2,5? edges:6-1,6-4,6-2,6-5? Actually edges: 6-1, 4-6, 6-2, 5-6. So yes. So from 6 we set dist for 4? dist4 =2 (through 6), dist2=2 (through 6). From 5: neighbors:3,4,6,5? edges:5-3,4-5,5-6. So dist3 =2 (through 5), dist4 already 2 maybe min. So distances: 1:0, 5:1,6:1, 2:2,3:2,4:2. Now check each node: Node2 (dist2) neighbors: edges:2-4,6-2. So neighbors:4(dist2),6(dist1) => pick 6. Node3 (dist2) neighbors: 5(dist1),4(dist2) => pick 5. Node4 (dist2) neighbors:3(dist2),2(dist2),6(dist1),5(dist1) => pick either 6 or 5. In example output they gave: Yes, then for room2:6, room3:5, room4:5, room5:1, room6:1. That matches: 2->6, 3->5,4->5,5->1,6->1. So okay.

    Thus solution is straightforward.

    But is there any scenario where even if each node has a neighbor with smaller distance, following signposts might not eventually reach 1? As argued, if each node points to a neighbor with strictly smaller distance, then starting from any node, distance decreases each step, and since distances are nonnegative integers, after at most dist steps you'll reach a node with distance 0, which must be node 1 (only node with distance 0). But is it possible that node 1 could have distance 0, but could there be other nodes with distance 0? No, distance from 1 is defined as shortest path length; only node 1 has distance 0. So termination is guaranteed.

    Thus algorithm is correct.

    Now implement:

    • Read N,M.
    • Build adjacency list: vector<vector> g(N+1).
    • For each edge: add both ends.
    • BFS from 1: queue, vector dist(N+1, -1). dist[1]=0. Push 1. While queue not empty: pop u, for each v in g[u]: if dist[v]==-1, set dist[v]=dist[u]+1, push v.
    • After BFS, for i from 2 to N:
      • For each neighbor v of i: if dist[v] == dist[i]-1: set ans[i]=v; break.
      • If after loop ans[i] is still 0 (or not set), then impossible => print No and exit.
    • Print Yes and then for i=2..N: print ans[i].

    Complexities: O(N+M).

    But careful: For node i, we might search all neighbors. That could sum to O(M). That's fine.

    Now check for potential pitfalls: BFS might be done with unweighted graph, but graph is undirected and connected, so BFS works.

    But the problem statement: "minimum number of passages possible" suggests shortest path in terms of number of edges, which is BFS.

    Now, what about if there are multiple edges? Still fine.

    Thus solution is straightforward.

    But wait: The problem might be trickier: The signpost assignment must guarantee that for each node, the path obtained by following signs is a shortest path to 1, but what if there is a node that has a neighbor with distance -1? That's not possible.

    Thus answer.

    But we should double-check the condition: "If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible." It doesn't explicitly say that you must not pass through any node twice or that the path must be simple; but following signposts yields a deterministic sequence. Could it loop? If we assign incorrectly, it could loop or never reach 1. But with our assignment, it's a decreasing distance so no loops.

    Now, is there any additional requirement that the signpost in each room must point to a directly connected room? Yes, we already ensure that.

    Thus solution is correct.

    Now I'll write the answer in Python.

    Implementation details:

    • Use sys.stdin.read to parse input quickly.
    • Build adjacency as list of lists.
    • BFS using collections.deque.
    • Distances as list of ints, size N+1.
    • ans = [0]*(N+1)
    • For i in range(2,N+1):
      • found = False
      • for nb in g[i]: if dist[nb] == dist[i]-1: ans[i]=nb found=True break
      • if not found: print("No") and exit.
    • Print "Yes"
    • Then for i in range(2,N+1): print(ans[i])

    One nuance: For nodes with distance 1, dist[i]-1 = 0, so they need a neighbor with distance 0, which must be node 1. So ans[i] = 1 if edge to 1 exists. Graph is connected so all dist 1 nodes are directly connected to 1? Actually they could have distance 1 if there is a direct edge to 1. In a BFS from 1, nodes at distance 1 are those with a direct edge to 1. So yes, they have neighbor 1 with dist 0. So fine.

    Thus answer.

    But what about nodes that are unreachable? Graph is connected so all reachable.

    Now time complexity: O(N+M). Memory: O(N+M). Fine.

    Now I'll produce final answer.

    But before final, let's test on given examples.

    Example1:

    N=4 M=4 edges. BFS: dist[1]=0; queue:1; neighbors:2 dist[2]=1; queue:2; from 2: neighbors 1 (visited),3 (set dist[3]=2),4? Actually edge 2-4? Input: 4 2, so yes 2-4, set dist[4]=2; then process 3: neighbors 2 (dist2),4 (dist2) no new; 4: neighbors 3,2 no new. So dist = [?,0,1,2,2]. Then for node2: dist=1, neighbors:1(dist0) -> ans2=1. Node3: dist=2, neighbors:2(dist1) and 4(dist2) -> pick 2. Node4: dist=2, neighbors:3(dist2),2(dist1) -> pick 2. Output matches.

    Example2: as above.

    Edge case: If graph is tree, there is exactly one parent in BFS tree (except possibly multiple if same depth? In tree, each node has exactly one parent if we root at 1; but BFS tree may have multiple if there are multiple paths? Actually tree has unique simple paths, so each node (except 1) has exactly one neighbor closer to root (its parent) and others are farther. So assignment is unique: point to parent. That's valid.

    Edge case: If graph has a node that is at distance d, but all its neighbors are at distance d or d+1? Actually because it's BFS, there must be at least one neighbor at distance d-1? Not necessarily. For a node v with distance d, by definition there exists a shortest path from 1 to v of length d; the node before v on that path is a neighbor u with distance d-1. So there must be at least one neighbor with distance d-1. So condition should always be satisfied? Wait, is it always true that for any node v (except 1) there is at least one neighbor u such that dist[u] = dist[v] - 1? By definition of shortest path distances: The distance from 1 to v is d, so there exists at least one path of length d. The node immediately preceding v on that path is a neighbor of v, and its distance is d-1. So indeed such neighbor exists. So it seems impossible to have a node without a neighbor with distance d-1. But careful: The BFS distances are computed from 1, and since the graph is undirected, if v has distance d, there must be a neighbor u on some shortest path from 1 to v with distance d-1. Because take a shortest path (v0=1, v1,..., vd=v). Then v_{d-1} is adjacent to v and has distance d-1. So the condition is automatically satisfied for all nodes. Therefore, the answer should always be Yes? However, the problem statement includes possibility of printing No, so maybe there is a catch. Let's think: The signpost must point to a directly connected room. And we need that following signposts yields a shortest path. The existence of a neighbor with smaller distance is necessary, but as argued, it's always present. So why would No be possible? Maybe the catch is that the signpost assignment must be consistent for all nodes simultaneously? But we are assigning independently per node. The condition for each node is independent: It only cares about the signpost in that node and the resulting path. There's no requirement that the signposts form a tree or that they don't create cycles? But if each node points to a neighbor with strictly smaller distance, then cycles cannot happen because distances strictly decrease along any path of signposts. So there can't be a cycle. So it seems always possible.

    Wait, maybe I misinterpreted: "If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible." This might be interpreted as: For each node v (except 1), the path obtained by following the signposts must be a shortest path from v to 1. That's what we used. And we argued that existence of a neighbor on a shortest path is guaranteed. So why would there be No? Let's double-check the problem statement and constraints. The only nuance might be: "the minimum number of passages possible" might refer to the absolute shortest path length in the original graph, but also the signpost path must not only be of length equal to the shortest distance, but also must not be longer than that; but we ensure each step goes to a node with distance one less, so the number of steps equals the distance. So that's fine.

    But maybe the signpost must be placed in each room except Room 1, but the condition must hold for each room except Room 1. However, the signpost in room i points to a directly connected room; but it could be that the path eventually reaches room 1, but does it guarantee that it uses the minimum number of passages? For that, each step must go to a neighbor that reduces distance by exactly 1. But if a node v points to a neighbor u with dist[u] = dist[v] - 1, then from v, the first step goes to u, then from u we follow its signpost. But what if u's signpost points to some w that does not have dist[w] = dist[u] - 1? That could cause the path from v to be longer than dist[v] because from u onward the path might not be optimal. The condition for each node v requires that the entire path from v to 1, following signposts, has length equal to the minimum possible. So it's not enough that v's immediate neighbor is on a shortest path; the subsequent signposts must also lead optimally to 1. Because if u's signpost points to some node x with dist[x] = dist[u] (or higher), then from u onward the path may be longer than dist[u]. Therefore, to satisfy condition for v, we need that for all nodes on the path, their signposts also point to a node with smaller distance, eventually reaching 1 optimally. However, the condition must hold for each node individually. So if we assign each node (except 1) a neighbor that is closer to 1 (dist-1), then for any starting node v, the sequence of distances will strictly decrease by at least 1 each step (could it decrease by more? Actually if we point to a neighbor with distance dist-1, the step reduces distance by exactly 1). So after k steps, we reach a node with distance dist(v)-k. Eventually we reach distance 0 at node 1. The number of steps equals dist(v). So it is a shortest path. But this relies on the fact that from the neighbor u, its signpost also points to a node with distance dist(u)-1. But what if u points to a node with distance dist(u)-1? We ensured that for all nodes (except 1) we pick a neighbor with distance one less. So yes. So if we assign every node a neighbor with dist-1, then the path from any node will be a shortest path. So condition holds for all.

    So the only requirement is that for each node v != 1, there exists at least one neighbor with distance dist(v)-1. And as argued, that always exists. So answer should always be Yes. Then why does the problem allow output "No"? Possibly because the graph might have multiple components? But constraints say it's connected. So always connected.

    Maybe I'm missing something: The signpost must point to one of the rooms directly connected to that room. That's fine. But perhaps the condition "after traversing the minimum number of passages possible" means that the path taken must be exactly a shortest path, but also that it must be the shortest possible among all possible sequences of moves that follow signposts? That seems tautological.

    Alternatively, maybe the interpretation is different: The signpost assignment is global, and the condition must hold for each room simultaneously. That is, for each room v, if you follow signposts from v, you eventually reach room 1, and the number of passages traversed in that specific journey equals the minimum possible distance from v to 1 in the graph. This is what we used.

    Given that distances from BFS always guarantee a neighbor with dist-1, why would there be a No? Unless there's a twist: The signpost assignment must be made before we know the distances? But distances are determined by the graph.

    Wait, maybe the "minimum number of passages possible" refers to the minimum possible number of passages that you have to traverse from that room to reach Room 1, considering that you are allowed to choose your path freely, not restricted by signposts. That is the shortest path distance. So as above.

    But maybe there is a scenario where a node v has dist(v) = d, and there exists a neighbor u with dist(u)=d-1, but if we assign v->u, then from u, the signpost might not lead to a shortest path? However, the condition for u separately requires that from u, the signpost path also be a shortest path. So we must assign for u some neighbor w with dist(w)=dist(u)-1. If we assign u->w, then indeed the path from v is v->u->w... This will be a shortest path provided each step reduces distance by 1. So it's fine.

    But what if there is a node that has no neighbor with dist-1? Could that happen? Let's examine: Suppose we have a node v with distance d. Consider any shortest path from 1 to v. The last edge connects some node u (distance d-1) to v. So v is adjacent to u. So such u exists. Therefore, there is always at least one neighbor with dist-1. So it's impossible to have no such neighbor. So answer always Yes. Then why would problem include No? Possibly because of the input format: The graph is not necessarily connected? But constraints say "One can travel between any two rooms by traversing passages." So it's connected.

    Maybe there is another nuance: The signpost in each room must point to exactly one room. That's what we do. The condition "you will reach Room 1 after traversing the minimum number of passages possible." Could be interpreted as: The path you take by following signposts must be a shortest path, but also you must not be able to reach Room 1 with fewer passages by deviating from the signposts? That's trivial.

    Alternatively, maybe the problem expects to output "No" when there is a node that has multiple possible parents but also the assignment must be such that the resulting directed graph is acyclic and leads to 1, which is always possible if we pick a parent. So always Yes.

    Wait, look at problem statement again: "If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible." It does not say "exactly the minimum number", but "after traversing the minimum number of passages possible." That might mean that the number of passages you traverse along the signpost-following path equals the minimum possible distance from that room to room 1. That's what we think.

    I recall similar problems: AtCoder problem "Signpost" maybe? Actually I think this is from AtCoder Beginner Contest 168? Or something like "Cave". Let me search memory: There's a known problem "Cave" where you need to assign signposts such that following them leads to room 1 along a shortest path. I think I've seen it: AtCoder ABC 168 F? Not sure. But I recall a problem where answer is always Yes because you can just use BFS tree. But many participants might think about cycles, but it's always possible. However, they included "No" possibly for cases where distances are not defined? No.

    Let's test with a tricky graph: Suppose there is a node that is directly connected to 1 (distance 1). It must point to 1. That's fine. Suppose there is a node at distance 2, but its only neighbor with distance 1 is node A, but node A may have no neighbor with distance 0 except 1? But node A is distance 1, so it is adjacent to 1. So it's fine. So always possible.

    Thus the answer is always Yes for any connected graph. But why then sample input/output shows "Yes"? They didn't provide a "No" sample, but it's possible they omitted. Could there be a case where it's impossible? Let's consider if the graph has self-loops? No. Parallel edges? Not an issue.

    Maybe I misinterpret: The signpost must point to a room directly connected, but the condition says: "If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible." That means that the path taken by following signposts must be exactly a shortest path, but it must also be the case that the number of passages traversed is the minimum possible, which is the distance. That's what we have.

    But perhaps there's a subtlety: The "minimum number of passages possible" might be interpreted as the minimum number of passages you need to traverse if you are allowed to choose your path freely at each step (i.e., without any restrictions). That is the distance. So we're good.

    Thus answer always Yes. But wait, is there a scenario where a node v has distance d, but all its neighbors with distance d-1 lead to a node u that, if we assign v->u, then from u, no matter which neighbor we assign (including possibly v) could cause a problem? But we assign all nodes independently. For node u, we will assign a neighbor with distance d-2 (or 0 if d-1=0). So it won't point back to v if v has distance d (which is larger). Because we will choose a neighbor with distance exactly dist(u)-1, which is d-2 (if d>1). So it won't be v because dist(v)=d > d-2. So no cycles.

    Thus always possible.

    Maybe the catch is that we must place a signpost in each room except Room 1, but we don't place a signpost in Room 1. The condition only applies to rooms except Room 1. So it's fine.

    Thus the answer is always Yes, and we can just output any parent from BFS tree. But is it always valid to output any neighbor with dist-1? Yes.

    But why then did they ask to determine whether there is a way? Possibly because they want to test BFS and awareness that it's always possible. But it's too trivial? Could there be a scenario where following signposts leads to a loop before reaching 1 even if each node points to a neighbor with smaller distance? That can't happen because distances are strictly decreasing.

    Let's double-check: Suppose we have nodes A and B both with distance 2, and we set A->B and B->A. Then distances: dist(A)=2, dist(B)=2, but A points to B which has distance 2, not less. That violates our rule. So our rule prevents that. So we must pick neighbors with strictly smaller distance.

    Now is it always possible to pick such neighbors? As argued yes because there is always at least one neighbor with smaller distance (on some shortest path). But wait: Consider a node v with distance d. The neighbor on a shortest path has distance d-1. However, that neighbor might be node 1 only if d=1. Otherwise it's some other node. So it exists. So always possible.

    Thus answer always Yes. But why would problem say "Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists."? Because maybe there is a scenario where the graph is directed? But it's undirected. Could be that they meant something else: The signpost in each room points to one of the rooms directly connected, but the signpost is placed and then you follow them. The objective: For each room, the path obtained by following signs must be a shortest path to room 1. However, note that the path is determined by the signposts, which are fixed. So for each room, the sequence of rooms visited must be a shortest path. That is what we used.

    Is there any hidden condition that the signposts must be placed such that for each room, the path is the minimum possible, but maybe the path must be exactly one of the shortest paths, and it must be unique? No.

    Maybe there is an additional condition that the signposts should point to a room that is closer in terms of the minimum number of passages, but not necessarily exactly distance-1? Consider: If a node points to a neighbor with distance d-2, then the distance would reduce by 2, making the total steps from v to 1 less than dist(v)? That would be impossible because the minimum number of steps is dist(v). If you reduce by 2 in one step, you might reach a node with distance d-2, then you'd need at least d-2 more steps, total at least d-1? Actually if you go from v (dist d) to u (dist d-2) in one step, that means there is an edge between v and u, and dist(u)=d-2. Then the shortest path from u to 1 is d-2, so total steps from v to 1 via u would be 1 + (d-2) = d-1, which is less than d. But that's impossible because dist(v)=d is the minimum number of steps to reach 1. So such an edge cannot exist. Because if there is an edge from v to u with dist(u)=d-2, then we could go from 1 to u in d-2 steps, then from u to v in 1 step, giving a path from 1 to v of length d-1, contradicting that dist(v)=d. So such an edge cannot exist. So any neighbor of v must have distance either d-1, d, or d+1 (by BFS property). It cannot be less than d-1. So the only possible neighbor with strictly smaller distance is exactly d-1. So our condition is both necessary and sufficient.

    Thus always possible.

    But wait, could there be a node v where the only neighbor with distance d-1 is such that if we assign v to that neighbor, then later from that neighbor the path might not be optimal? But we can also assign that neighbor to something else. As long as we assign all nodes to a neighbor with distance-1, it's consistent.

    Thus answer always Yes.

    Given this, maybe the problem originally had a twist: The signpost must point to a room directly connected, and the condition must hold for each room, but perhaps the signposts are placed in all rooms including Room 1? But they said except Room 1. So 1 has no signpost, so it's the destination.

    Maybe there is a scenario where the graph is not connected? But they said it's connected.

    So I'm leaning that the answer is always Yes. But let's verify with an extreme case: N=2, M=1, edge 1-2. dist1=0, dist2=1. Node2 must point to 1. That's valid. Yes.

    Another: N=3, edges: 1-2, 2-3, 1-3. Distances: 1:0, 2:1, 3:1? Actually 1-3 directly, so dist3=1. Node2 points to 1. Node3 points to 1. Yes.

    Thus always Yes.

    But perhaps the problem includes the possibility that the signpost in each room must point to a different room? No.

    Given that, the solution is trivial: BFS and output parent. But why would they ask to determine if it's possible? Could be they expect to handle cases where distances aren't defined due to multiple components? But constraints say connected.

    Alternatively, maybe the "minimum number of passages possible" means that the path taken by following signposts must be such that at each step, you move to a room that is as close as possible to 1 (greedy), i.e., you always go to the neighbor with smallest distance, but the signpost must be set so that following it yields the globally optimal path. That is essentially the same.

    Maybe there is a nuance: The signpost assignment must be such that for each room, the path you get by following signs is a shortest path, but you cannot change signposts per room; they are fixed globally. So it's the same.

    Thus I'm confident answer is always Yes.

    But wait, I recall a similar problem from AtCoder: ABC 168 F - . (Actually I remember a problem "Signpost" from JOI or something? Not sure.) However, I've seen a problem called "Signpost" on AtCoder? Actually AtCoder Beginner Contest 168 problem D: .. (D was ".. .." No). There is a problem "D - .." in ABC 168? Let's think: ABC 168 D is ".. .. .."? I recall a problem about placing signs to guide to room 1. I think it's ABC 168 D: "..-.." Actually I recall ABC 168 D was "..-.." not sure. I can search my memory: AtCoder ABC 168 D was "..-.."? Actually I think it was "D - ..-.."? Wait, ABC 168 D was ".. .. (Something)"? I'm trying to recall: There's a well-known problem "D - ..-.." from ABC 168? No.

    Maybe it's from AtCoder "ARC 106 B" or something? Eh.

    Actually, there is a known problem: "Signpost" from JOI 2020? Not sure.

    But I'm pretty confident it's always Yes.

    I'll double-check the problem statement: "Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists." So they are allowing "No". But maybe there is a scenario where it's impossible because the signpost must point to a directly connected room, and the condition must hold for each room, but maybe it's required that the signpost path is exactly a shortest path, and also that the signpost path must be unique? No.

    Maybe I misinterpret "minimum number of passages possible". Could it mean that the path you take by following signposts must be the shortest among all possible signpost placements? That doesn't make sense.

    Maybe it means: For each room, if you start there and follow signposts, you will reach Room 1, and the number of passages you traverse in that process is the minimum possible (over all possible ways of moving, not necessarily following signposts). That's what we used.

    Thus answer always Yes.

    But I'm uneasy: Perhaps the graph could have negative cycles? No.

    Maybe the signposts are placed before the graph is known? No.

    Given that the problem is from some contest, it's likely that the intended solution is BFS and output parent, and they might have included "No" just for completeness, but it will never happen given constraints. But could there be a scenario where the graph has multiple components? The problem states "One can travel between any two rooms by traversing passages." So it's connected.

    Thus, answer is always Yes.

    But I'll re-check: The input constraints: N up to 1e5, M up to 2e5. They could have made a test where for some node, all neighbors have the same distance? That's possible for nodes that are on a cycle of odd length? But still there must be at least one neighbor with smaller distance because of the definition of distance. Wait, consider a node v with distance d. Could it be that all its neighbors have distance d? That would mean no neighbor is closer. But then how could its distance be d? If all neighbors have distance >= d, then the shortest path to v would be at least d+1? Actually BFS distances: If v has distance d, then there exists at least one neighbor with distance d-1. Proof: BFS from 1: when we first discover v at distance d, it is via an edge from a node u that was discovered at distance d-1. That node u is a neighbor of v. So there is at least one neighbor with distance d-1. So it's impossible for a node to have all neighbors with distance >= d. So at least one neighbor has distance d-1.

    Thus always possible.

    Hence the answer is always Yes, and we just need to output any neighbor with distance-1.

    But wait: The BFS might discover v from multiple nodes; the first time it's discovered, it's via a neighbor with distance d-1. That neighbor may have been assigned a distance earlier. So yes.

    Thus solution is trivial: BFS and for each node except 1, output any neighbor that was discovered earlier (i.e., parent in BFS tree). Actually we can just output the parent from BFS tree when we first discovered the node. That's a valid assignment. So we can do BFS and record parent.

    Implementation: BFS from 1, for each node when we first set its distance, we set its parent as the node we came from. That gives a BFS tree. Then for each node v (2..N), output its parent. This automatically ensures that dist[parent] = dist[v] - 1. And it's valid.

    But careful: Could there be nodes that are discovered via multiple parents? Yes, but we just record the first one. That's fine.

    Thus we can output the BFS parent.

    That is simpler.

    Now confirm: For node v, its parent is a neighbor with distance dist(v)-1. So condition satisfied.

    But is it necessary that for nodes that are discovered later but maybe the parent we recorded is not the one that gives a shortest path? Actually it is a shortest path because BFS ensures that.

    Thus the solution is simply BFS and output parents.

    Now the problem statement says "print the integer representing the room indicated by the signpost in Room i" for i from 2 to N. So we output the parent for each.

    So final answer: BFS, record parents, print Yes and then parents for 2..N.

    But what about nodes that are not reachable? Graph connected so all reachable.

    Thus we don't even need to check existence of a neighbor with dist-1 because BFS will assign one.

    But to be safe, after BFS, we could check that all nodes have dist assigned (they will). And then for each node v != 1, we could check that it has at least one neighbor with dist-1. But it's guaranteed by BFS.

    Hence solution: BFS, store parent, print Yes and parents.

    Now let's test with sample:

    Sample1: BFS from 1: start at 1. Process 1: neighbors: 2 (dist2 set to 1, parent[2]=1). Queue:2. Process 2: neighbors:1 visited,3 (dist3=2, parent[3]=2),4 (dist4=2, parent[4]=2). So parents:2->1,3->2,4->2. Output: Yes, then for 2:1, 3:2, 4:2. Matches.

    Sample2: BFS from 1: start at 1. neighbors:6 (dist6=1, parent[6]=1),5 (dist5=1, parent[5]=1). Queue:6,5. Process 6: neighbors:1 visited,4 (dist4=2, parent[4]=6),2 (dist2=2, parent[2]=6). Process 5: neighbors:3 (dist3=2, parent[3]=5),4 (already dist2, but parent[4] already set as 6; we could also set parent[4]=5 if we process later, but BFS order maybe 6 first, so parent[4]=6). So parents:2->6,3->5,4->6,5->1,6->1. Output: Yes, then 2:6,3:5,4:6,5:1,6:1. That differs from sample output which had 4->5, 5->1,6->1,2->6,3->5. But that's okay because any valid assignment works. Sample output had 4->5, which is also valid because 5 is neighbor with dist1. In BFS we got 4->6, which is also valid. So both correct.

    Thus solution is correct.

    Now, is there any scenario where the BFS parent method fails? No.

    Thus answer is always Yes.

    But wait, the problem statement says "Determine whether there is a way ... and print one such way if it exists." Could there be a case where it's impossible? Possibly if the graph is directed? But it's undirected.

    Maybe the signpost must point to a room directly connected, but you cannot point to a room that is the same as the current? No.

    Maybe there is a nuance: "the minimum number of passages possible" might mean the minimum possible number of passages you need to traverse given the signposts, i.e., the signposts are fixed, and you are forced to follow them. The condition is that for each room, the number of steps to reach 1 by following signposts is exactly the graph distance. That's our interpretation.

    But is it possible that for some node, all neighbors with distance-1 are such that if you point to them, then from that neighbor, following its signpost might not lead to a shortest path? However, the condition for each node is independent: It must hold for node v that following signposts from v yields a shortest path. It does not require that the signpost path from v is the same as the path from u. It only requires that the sequence of rooms visited from v, determined by the signposts, ends at 1 and its length equals dist(v). So if v points to u (with dist(u)=dist(v)-1), and if from u the signpost path length to 1 is dist(u) (i.e., it is a shortest path), then total steps from v is 1 + dist(u) = 1 + (dist(v)-1) = dist(v). So it's sufficient that from u, the signpost path is a shortest path. And since we enforce the same rule for all nodes, it will be.

    But what if we assign u to some w that is not on a shortest path? That would cause the path from u to be longer than dist(u), which would cause the path from v to be longer than dist(v). So we must assign all nodes to point to a neighbor with distance-1. So the assignments are interdependent. However, as argued, it's always possible to assign all nodes to a neighbor with distance-1. So it's consistent.

    Thus answer is always Yes.

    Hence we can just output BFS parent.

    But wait: In BFS, we assign parent for each node when first discovered. That yields a tree where each node (except root) has a parent with distance-1. So that's a valid assignment. So yes.

    Thus final code: BFS from 1, record parent, print Yes, then parents[2..N].

    But there is a subtle point: The graph is connected, so BFS will visit all nodes.

    Time complexity: O(N+M).

    Now, before writing final answer, I'll think about whether there could be a case where BFS from 1 gives distances, but for some node, the parent we recorded may not be a neighbor? It is because we discovered via that neighbor, so it's a neighbor.

    Alright.

    Now, could there be a scenario where BFS is not unique and we might inadvertently assign a parent that is not directly connected? No.

    Thus solution is simple.

    But let's re-read problem: "The signpost in each room will point to one of the rooms directly connected to that room with a passage." So we must point to a neighbor. BFS parent is a neighbor. Good.

    Thus final answer.

    Now, the problem might be from AtCoder ABC 168 D? Actually I recall ABC 168 D was "..-.." maybe "D - ..-.." It was "D - ..-.."? Wait, I remember a problem: "ABC 168 D - ..-.." but I'm not sure. Actually ABC 168 D was "D - ..-.."? Let's recall: ABC 168 had problems: A, B, C, D, E, F. D was "D - ..-.."? I think ABC 168 D was "D - ..-.."? No, I'm mixing.

    Better check memory: There is a known problem "ABC 168 D - ..-.." but I think it's "D - ..-.."? Actually I recall a problem about "signpost" or "guidance" from AtCoder: "ABC 168 D - ..-.."? I think it's "D - ..-.."? Hmm.

    Anyway, it's fine.

    Thus the solution is to output BFS tree.

    But I'm still bothered by the presence of "No". Could there be a scenario where the graph is directed? The problem says passages connect rooms bidirectionally. So undirected.

    Maybe there is a nuance: The signpost must point to a directly connected room, but the condition "after traversing the minimum number of passages possible" might be interpreted as "you will eventually reach Room 1, and the number of passages you traverse in that process is the minimum possible among all possible ways of placing signposts"? That doesn't make sense.

    Alternatively, maybe the signpost assignment must be such that for each room, following signposts gives a path that is a shortest path, but also the signposts must be placed simultaneously and cannot be changed per room? That's what we did.

    Given all that, I'm confident that answer is always Yes.

    Thus implementation: BFS.

    But wait, there is a possibility: The graph may have multiple edges or self-loops? Constraints say A_i != B_i, so no self-loops, but multiple edges possible? Not prohibited, but doesn't affect.

    One more nuance: The signpost must point to a neighbor, but what if the neighbor is the same as the current? Not allowed.

    Alright.

    Now I'll produce the final answer.

    But I want to consider if there is any trick: The signpost path must be the minimum number of passages possible. That means that for each node, the number of steps to reach 1 by following signposts must be exactly the distance. Suppose we have a node v with distance d, and we point it to u with dist(u)=d-1. If from u, the signpost path length is > d-1, then total > d. So we need to ensure that for every node, its signpost path length equals its distance. This is equivalent to constructing a functional graph from all nodes except 1, where each node points to a neighbor with distance exactly one less. This ensures that the distance to 1 along the pointers is exactly the distance, because from node v, following pointers will give a path v -> p(v) -> p(p(v)) -> ... until reaching 1. Since each step reduces distance by exactly 1, after k steps we reach a node with distance d-k. When we reach a node with distance 0, it must be node 1 (since only node with distance 0). So the number of steps is exactly d. So it's sufficient that p(v) is a neighbor with dist(p(v)) = dist(v)-1. And this condition is also necessary? If p(v) has distance less than dist(v)-1, that's impossible. If p(v) has distance exactly dist(v)-1, then as argued, if all nodes satisfy this, then the path length from v is exactly dist(v). So necessary and sufficient.

    Thus the problem reduces to assigning for each node v != 1 a neighbor u with dist(u) = dist(v)-1. Since such neighbor always exists, answer always Yes.

    Thus code.

    Now I'll implement in Python.

    Edge Cases: Large input, so use sys.stdin.buffer.read and parse ints. Use deque for BFS.

    Implementation steps:

    • import sys, collections
    • data = sys.stdin.buffer.read().split()
    • it = iter(data)
    • N = int(next(it)); M = int(next(it))
    • g = [[] for _ in range(N+1)]
    • for _ in range(M): a = int(next(it)); b = int(next(it)) g[a].append(b) g[b].append(a)
    • dist = [-1]*(N+1)
    • parent = [0]*(N+1)
    • q = collections.deque()
    • dist[1] = 0
    • q.append(1)
    • while q: u = q.popleft() for v in g[u]: if dist[v] == -1: dist[v] = dist[u] + 1 parent[v] = u q.append(v)
    • Now after BFS, we have parent for all nodes except 1.
    • But we should verify that all nodes have dist != -1 (connected). Since graph is connected, it's fine.
    • Print "Yes"
    • For i in range(2,N+1): print(parent[i])

    That's it.

    But wait: There is a possibility that BFS may assign parent for node i but that parent may be not a neighbor with dist-1? Actually by BFS, when we set dist[v] = dist[u] + 1, then dist[u] = dist[v]-1. So it's correct.

    Thus final.

    But perhaps there is a nuance: The problem expects that if there is no way, output "No". We think it's always Yes, but to be safe, we could check for each node if there is at least one neighbor with dist-1. But it's unnecessary. However, I'll include a check and if any node fails, print "No". But that will never happen. But it's okay to include for robustness.

    Thus final code:

    def solve():
        import sys
        from collections import deque
        data = sys.stdin.buffer.read().split()
        it = iter(data)
        N = int(next(it)); M = int(next(it))
        g = [[] for _ in range(N+1)]
        for _ in range(M):
            a = int(next(it)); b = int(next(it))
            g[a].append(b)
            g[b].append(a)
        dist = [-1]*(N+1)
        parent = [0]*(N+1)
        q = deque([1])
        dist[1] = 0
        while q:
            u = q.popleft()
            for v in g[u]:
                if dist[v] == -1:
                    dist[v] = dist[u]+1
                    parent[v] = u
                    q.append(v)
        # Optionally check for any node without parent (except 1)
        for i in range(2,N+1):
            if parent[i]==0: # should not happen, but if graph not connected?
                print("No")
                return
        print("Yes")
        out = []
        for i in range(2,N+1):
            out.append(str(parent[i]))
        sys.stdout.write("\n".join(out))
    if __name__ == "__main__":
        solve()
    

    But note: The check parent[i]==0 might be insufficient because parent[i] could be 0 only if not visited. Since graph is connected, all visited. However, if there is a node that is visited but parent is not set? BFS sets parent when first visited. So all nodes except 1 get parent set. So fine.

    Alternatively, we could check if any node v (except 1) has no neighbor with dist-1, but that's redundant.

    Now, some might argue that BFS parent assignment is not sufficient if the graph is not a tree? But it's sufficient because parent is a neighbor with dist-1.

    Thus answer.

    But wait: Could there be a scenario where for a node v, the parent we assigned (the first discovered neighbor) is not directly connected? It is.

    Thus final.

    Now, I'll reflect: The problem seems too trivial for AtCoder? It might be a D problem, but still doable. However, I recall a problem "D - .." from ABC 168 that is exactly this: "D - ..-.." Actually ABC 168 D is "D - ..-.." maybe "D - ..-.."? I'll search memory: ABC 168 D was "D - ..-.."? I think it was "D - ..-.."? I recall a problem: "D - ..-.." is about "signpost"? Wait, AtCoder Beginner Contest 168 D is "D - ..-.."? I think it's "D - ..-.."? Actually I'm trying to recall the title: There is "D - ..-.." in ABC 168? Let's check: ABC 168 problems: A - ∴ (Therefore), B - ...? I'm not sure. Actually I think ABC 168 D was "D - ..-.."? I'm going to think of a known problem: "D - ..-.." from ABC 168: The problem statement about "rooms and corridors" and "signposts" sounds exactly like AtCoder Beginner Contest 168 D: "D - ..-.." maybe? Actually I'm pretty sure I've seen this: There is a problem called "D - ..-.." in ABC 168? Let's search memory: I recall solving a problem where you need to output "Yes" and then parents from BFS. That was ABC 168 D: "D - ..-.."? I think it was "D - ..-.."? Actually I'm mixing with ABC 168 D: "D - ..-.."? I think ABC 168 D was about "..-.." and it was exactly this: "Cave" maybe? No, ABC 168 D was "D - ..-.."? Let's recall: AtCoder Beginner Contest 168 had a problem "D - ..-.." maybe "D - ..-.."? Actually the contest might have been ABC 168 D: "D - ..-.."? I'd better stop.

    Anyway, solution is fine.

    But there is a nuance: The problem states "print N lines. The first line should contain Yes, and the i-th line (2 ≤ i ≤ N) should contain the integer representing the room indicated by the signpost in Room i." So we must output exactly N lines: first line "Yes", then for i=2..N output the neighbor. So we output N lines total. That's what we did.

    Now final answer.

    I will now produce the final answer. ```python

    import sys from collections import deque

    def solve() -> None: data = sys.stdin.buffer.read().split() it = iter(data) N = int(next(it)) M = int(next(it))

    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        a = int(next(it))
        b = int(next(it))
        g[a].append(b)
        g[b].append(a)
    
    dist = [-1] * (N + 1)
    parent = [0] * (N + 1)
    
    q = deque([1])
    dist[1] = 0
    
    while q:
        u = q.popleft()
        for v in g[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    
    # The graph is guaranteed to be connected, so every room (except 1) has a parent.
    # If for some reason a room remained unvisited, we would output "No", but that never happens here.
    for i in range(2, N + 1):
        if parent[i] == 0:   # should not happen
            print("No")
            return
    
    out_lines = ["Yes"]
    for