Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

paths = [set() for _ in range(M)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    paths[a].add(b)
    paths[b].add(a)

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for else_room in paths[key_room]:
            if rooms[else_room] == -1:
                rooms[else_room] = step
                next_key_rooms.add(else_room)
                marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)

print('Yes')
for i in marks:
    print(i+1)

Fixed submission:
N, M = map(int, input().split())

paths = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    paths[a].add(b)
    paths[b].add(a)

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for else_room in paths[key_room]:
            if rooms[else_room] == -1:
                rooms[else_room] = step
                next_key_rooms.add(else_room)
                marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)

print('Yes')
for i in marks:
    print(i+1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

paths = set()
for _ in range(M):
    a, b = map(int, input().split())
    paths.add((a-1, b-1))

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    kick_list = []
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for path in paths:
            if key_room in path:
                else_room = path[0]
                if else_room == key_room:
                    else_room = path[1]
                kick_list.append(path)
                if rooms[else_room] == -1:
                    rooms[else_room] = step
                    next_key_rooms.add(else_room)
                    marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)
    for kick in kick_list:
        if kick in paths:
            paths.remove(kick)

flag = True
for room in rooms[1:]:
    if room == -1:
        flag = False
        print('No')
        break

if flag:
    print('Yes')
    for i in marks:
        print(i+1)


Fixed submission:
N, M = map(int, input().split())

paths = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    paths[a].add(b)
    paths[b].add(a)

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for else_room in paths[key_room]:
            if rooms[else_room] == -1:
                rooms[else_room] = step
                next_key_rooms.add(else_room)
                marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)

print('Yes')
for i in marks:
    print(i+1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

paths = set()
for _ in range(M):
    a, b = map(int, input().split())
    paths.add((a-1, b-1))

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    kick_list = []
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for path in paths:
            if key_room in path:
                else_room = path[0]
                if else_room == key_room:
                    else_room = path[1]
                kick_list.append(path)
                if rooms[else_room] == -1:
                    rooms[else_room] = step
                    next_key_rooms.add(else_room)
                    marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)
    for kick in kick_list:
        if kick in paths:
            paths.remove(kick)

flag = True
for room in rooms[1:]:
    if room == -1:
        flag = False
        print('No')
        break

if flag:
    print('Yes')
    for i in marks:
        print(i+1)


Fixed submission:
N, M = map(int, input().split())

paths = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    paths[a].add(b)
    paths[b].add(a)

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for else_room in paths[key_room]:
            if rooms[else_room] == -1:
                rooms[else_room] = step
                next_key_rooms.add(else_room)
                marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)

print('Yes')
for i in marks:
    print(i+1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

paths = set()
for _ in range(M):
    a, b = map(int, input().split())
    paths.add((a-1, b-1))

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    kick_list = []
    next_key_rooms = []
    for key_room in key_rooms[-1]:
        for path in paths:
            if key_room in path:
                else_room = path[0]
                if else_room == key_room:
                    else_room = path[1]
                kick_list.append(path)
                if rooms[else_room] == -1:
                    rooms[else_room] = step
                    next_key_rooms.append(else_room)
                    marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)
    for kick in kick_list:
        if kick in paths:
            paths.remove(kick)

flag = True
for room in rooms[1:]:
    if room == -1:
        flag = False
        print('No')
        break

if flag:
    print('Yes')
    for i in marks:
        print(i+1)


Fixed submission:
N, M = map(int, input().split())

paths = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    paths[a].add(b)
    paths[b].add(a)

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for else_room in paths[key_room]:
            if rooms[else_room] == -1:
                rooms[else_room] = step
                next_key_rooms.add(else_room)
                marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)

print('Yes')
for i in marks:
    print(i+1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

paths = set()
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    paths.add((a, b))

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
step = 1
for step in range(1, N):
    key_rooms = []
    for i, room in enumerate(rooms):
        if room == step-1:
            key_rooms.append(i)
    kick_list = []
    for key_room in key_rooms:
        for path in paths:
            if key_room in path:
                else_room = path[0]
                if else_room == key_room:
                    else_room = path[1]
                kick_list.append(path)
                if rooms[else_room] == -1:
                    rooms[else_room] = step
                    marks[else_room-1] = key_room
    for kick in kick_list:
        if kick in paths:
            paths.remove(kick)

flag = True
for room in rooms[1:]:
    if room == 0:
        flag = False
        print('No')
        break

if flag:
    print('Yes')
    for i in marks:
        print(i+1)

Fixed submission:
N, M = map(int, input().split())

paths = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    paths[a].add(b)
    paths[b].add(a)

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for else_room in paths[key_room]:
            if rooms[else_room] == -1:
                rooms[else_room] = step
                next_key_rooms.add(else_room)
                marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)

print('Yes')
for i in marks:
    print(i+1)