Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []


# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

# for a, b in zip(A, B):
#     route2[a - 1].append(b - 1)
#     route2[b - 1].append(a - 1)


# 隣接行列
route = [[0 for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = route[b - 1][a - 1] = 1


room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue)>0:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    # for i in route2[now]:
    #     if i not in visited:

    for i, node in enumerate(route[now]):
        if node == 0:
            continue
    #
        if i not in visited:

            # for r in route2[now]:
            # for r in range(N):
            #     if r not in visited:
            # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[i]:
                room_depth[i] = min(room_depth[now] + 1, room_depth[i])
            else:
                room_depth[i] = room_depth[now] + 1
            #
            # room_sign[i] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)


Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

route = [[0 for j in range(N)] for i in range(N)]

for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)
    
    route[_a - 1][_b - 1] = route[_b - 1][_a - 1] = 1

# # 隣接行列
# for i in range(N):
#     for j in range(N):
# 
# for a, b in zip(A, B):
#     route[a - 1][b - 1] = route[b - 1][a - 1] = 1

# # 隣接リスト
# route2 = [[] for n in range(N)]
#
# for a, b in zip(A, B):
#     route2[a - 1].append(b - 1)
#     route2[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for i, node in enumerate(route[now]):
        if node == 0:
            continue

        if i not in visited:

            # for r in route2[now]:
            # for r in range(N):
            #     if r not in visited:
            # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(i)
            visited.add(i)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[i]:
                room_depth[i] = min(room_depth[now] + 1, room_depth[i])
            else:
                room_depth[i] = room_depth[now] + 1

            room_sign[i] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)


Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 隣接行列
route = [[0 for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = route[b - 1][a - 1] = 1

# # 隣接リスト
# route2 = [[] for n in range(N)]
#
# for a, b in zip(A, B):
#     route2[a - 1].append(b - 1)
#     route2[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for i, node in enumerate(route[now]):
        if node == 0:
            continue

        if i not in visited:

            # for r in route2[now]:
            # for r in range(N):
            #     if r not in visited:
            # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(i)
            visited.add(i)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[i]:
                room_depth[i] = min(room_depth[now] + 1, room_depth[i])
            else:
                room_depth[i] = room_depth[now] + 1

            room_sign[i] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)


Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# # 隣接行列
# route = [[False for j in range(N)] for i in range(N)]
# 
# for a, b in zip(A, B):
#     route[a - 1][b - 1] = True
#     route[b - 1][a - 1] = True

# 隣接リスト
route2 = [[] for n in range(N)]

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque()
visited = []

queue.append(0)
visited.append(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)


    for r in route2[now]:
    # for r in range(N):
        if r not in visited:
        # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(r)
            visited.append(r)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[r]:
                room_depth[r] = min(room_depth[now] + 1, room_depth[r])
            else:
                room_depth[r] = room_depth[now] + 1

            room_sign[r] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)


Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 隣接行列
route = [[False for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = True
    route[b - 1][a - 1] = True

# 隣接リスト
route2 = [[] for n in range(N)]

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque()
visited = []

queue.append(0)
visited.append(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    
    for r in route2[now]: 
    # for r in range(N):
        if r not in visited:
        # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(r)
            visited.append(r)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[r]:
                room_depth[r] = min(room_depth[now] + 1, room_depth[r])
            else:
                room_depth[r] = room_depth[now] + 1

            room_sign[r] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)


Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 隣接行列
route = [[False for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = True
    route[b - 1][a - 1] = True

# room_connection = [[] for n in range(N)]
#
# for a, b in zip(A, B):
#     room_connection[a - 1].append(b - 1)
#     room_connection[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque()
visited = []

queue.append(0)
visited.append(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for r in range(N):
        if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(r)
            visited.append(r)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[r]:
                room_depth[r] = min(room_depth[now] + 1, room_depth[r])
            else:
                room_depth[r] = room_depth[now] + 1

            room_sign[r] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)


Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

room_connection = [[] for n in range(N)]

for a, b in zip(A, B):
    room_connection[a - 1].append(b - 1)
    room_connection[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]
visited = []
queue = deque()
queue.append(0)
# pprint(room_connection)

while stack:
    now =queue.popleft()
    # now = stack.pop()
    next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for r in next_room:
        if r not in visited:
            queue.append(r)
            # stack.append(r)

        if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            room_depth[r] = room_depth[now] + 1
            room_sign[r] = now + 1

    visited.append(now)

    if set(visited) == set(range(N)):
        break


    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)

Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

room_connection = [[] for n in range(N)]

for a, b in zip(A, B):
    room_connection[a - 1].append(b - 1)
    room_connection[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]
visited = []

# pprint(room_connection)

while stack:
    now = stack.pop()
    next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for r in next_room:
        if r not in visited or r not in stack:
            stack.append(r)

        if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            room_depth[r] = room_depth[now] + 1
            room_sign[r] = now + 1

    visited.append(now)

    if set(visited) == set(range(N)):
        break


    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)

Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

room_connection = [[] for n in range(N)]

for a, b in zip(A, B):
    room_connection[a - 1].append(b - 1)
    room_connection[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]
visited = []

while stack:
    now = stack.pop()
    next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for r in next_room:
        if r not in visited or r not in stack:
            stack.append(r)

        if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            room_depth[r] = room_depth[now] + 1
            room_sign[r] = now + 1

    visited.append(now)

    if visited == range(N):
        break

    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)

Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

room_next = [[] for n in range(N)]

for a, b in zip(A, B):
    room_next[a - 1].append(b - 1)
    room_next[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]
visited = []

while stack:
    # print('visited', visited)
    # print('next', stack)
    now = stack.pop()
    if now not in visited:
        visited.append(now)
        for r in room_next[now]:
            if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
                room_depth[r] = room_depth[now] + 1
                room_sign[r] = now + 1

                if r not in visited:
                    stack.append(r)

print('Yes')
for s in room_sign[1:]:
    print(s)

Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

room_next = [[] for n in range(N)]

for a, b in zip(A, B):
    room_next[a - 1].append(b - 1)
    room_next[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]
visited = []

while stack:
    now = stack.pop()
    if now not in visited:
        visited.append(now)
        for r in room_next[now]:
            if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
                room_depth[r] = room_depth[now] + 1
                room_sign[r] = now + 1
                stack.append(r)

print('Yes')
for s in room_sign[1:]:
    print(s)

Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
# BFS

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 接続している部屋のマップ
room_next = [[] for n in range(N)]

for a, b in zip(A, B):
    room_next[a - 1].append(b - 1)
    room_next[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]
visited = []

while stack:
    now = stack.pop()

    if now in visited:
        continue

    # print('now=', now)
    visited.append(now)
    for r in room_next[now]:
        if r not in visited:
            stack.append(r)

        if room_depth[r] is None:
            room_depth[r] = room_depth[now] + 1
            room_sign[r] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)


Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
# BFS

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 接続している部屋のマップ
room_next = [[] for n in range(N)]

for a, b in zip(A, B):
    room_next[a - 1].append(b - 1)
    room_next[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]
visited = []

while stack:
    now = stack.pop()
    visited.append(now)
    for r in room_next[now]:
        if r not in visited:
            stack.append(r)

        if room_depth[r] is None:
            room_depth[r] = room_depth[now] + 1
            room_sign[r] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)


Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 道の接続マップ
route2 = {}

# 接続している部屋のマップ
room_next = [[] for n in range(N)]

for a, b in zip(A, B):
    room_next[a - 1].append(b - 1)
    room_next[b - 1].append(a - 1)

# pprint(room_next)

# route2.update({(a - 1, b - 1): True})
# route2.update({(b - 1, a - 1): True})

# 探索する
room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

# 次に行く部屋
stack = [0]

while stack:
    now = stack.pop()
    for j in room_next[now]:
        # if (now, j) in route2.keys():
        if room_depth[j] is None or room_depth[j] > room_depth[now] + 1:
            room_depth[j] = room_depth[now] + 1
            room_sign[j] = now + 1
            stack.append(j)

print('Yes')
for s in room_sign[1:]:
    print(s)


Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 道の接続マップ
route2 = {}

for a, b in zip(A, B):
    route2.update({(a - 1, b - 1): True})
    route2.update({(b - 1, a - 1): True})

# 探索する
room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

# 次に行く部屋
stack = [0]

while stack:
    now = stack.pop()
    for j in range(N):
        if (now, j) in route2.keys():
            if room_depth[j] is None or room_depth[j] > room_depth[now] + 1:
                room_depth[j] = room_depth[now] + 1
                room_sign[j] = now + 1
                stack.append(j)

print('Yes')
for s in room_sign[1:]:
    print(s)


Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc168/tasks/abc168_d
N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 道の接続マップ
route = [[False for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = True
    route[b - 1][a - 1] = True


# 探索する
room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

# 次に行く部屋
stack = [0]
while stack:
    now = stack.pop()
    for j in range(N):
        if route[now][j]:
            # 次の部屋の深さが不明な場合または今の部屋の深さ+1より大きい場合は次の部屋の情報を更新
            if room_depth[j] is None or room_depth[j] > room_depth[now] + 1:
                room_depth[j] = room_depth[now] + 1
                room_sign[j] = now + 1
                stack.append(j)

print('Yes')
for s in room_sign[1:]:
    print(s)



Fixed submission:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)