Problem:
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.

Incorrect submission (verdict: Wrong Answer):

from collections import deque
def q4():
    class Room:
        def __init__(self, i):
            self.id = i
            self.d = -1
            self.next = []
            self.sign = -1

        def add_next(self, n):
            self.next.append(n)

        def print(self, tab=0, printed=[]):
            if self.id in printed:
                return
            printed.append(self.id)
            print("  " * tab + str(self.id) + f"({self.sign})")
            for n in self.next:
                n.print(tab + 1, list(printed))
    
        
    N, M = [int(i) for i in input().split(" ")]
    room_dict = {}

    def get_room(i):
        if i in room_dict:
            return room_dict[i]
        else:
            room = Room(i)
            room_dict[i] = room
            return room

    for i in range(M):
        A, B = [int(i) for i in input().split(" ")]
        get_room(A).add_next(get_room(B))
        get_room(B).add_next(get_room(A))


    d = 0
    sign = -1
    queue = deque([[get_room(1), d, sign]])
    while queue:
        room, d, sign = queue.popleft()
        if room.sign != -1:
            continue
        room.sign = sign
        room.d = d
        for n in room.next:
            queue.append([n, d + 1, room.id])

    for i in range(2, N + 1):
        print(get_room(i).sign)

q4()


Fixed, accepted submission:

from collections import deque
def q4():
    class Room:
        def __init__(self, i):
            self.id = i
            self.d = -1
            self.next = []
            self.sign = -1

        def add_next(self, n):
            self.next.append(n)

        def print(self, tab=0, printed=[]):
            if self.id in printed:
                return
            printed.append(self.id)
            print("  " * tab + str(self.id) + f"({self.sign})")
            for n in self.next:
                n.print(tab + 1, list(printed))
    
        
    N, M = [int(i) for i in input().split(" ")]
    room_dict = {}

    def get_room(i):
        if i in room_dict:
            return room_dict[i]
        else:
            room = Room(i)
            room_dict[i] = room
            return room

    for i in range(M):
        A, B = [int(i) for i in input().split(" ")]
        get_room(A).add_next(get_room(B))
        get_room(B).add_next(get_room(A))


    d = 0
    sign = -1
    queue = deque([[get_room(1), d, sign]])
    while queue:
        room, d, sign = queue.popleft()
        if room.sign != -1:
            continue
        room.sign = sign
        room.d = d
        for n in room.next:
            queue.append([n, d + 1, room.id])

    print("Yes")
    for i in range(2, N + 1):
        print(get_room(i).sign)

q4()