Problem:


Score: 400 points

Problem Statement

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.

Sample Input 1

4 4
1 2
2 3
3 4
4 2

Sample Output 1

Yes
1
2
2

If we place the signposts as described in the sample output, the following happens:

Starting in Room 2, you will reach Room 1 after traversing one passage: (2) \to 1. This is the minimum number of passages possible.

Starting in Room 3, you will reach Room 1 after traversing two passages: (3) \to 2 \to 1. This is the minimum number of passages possible.

Starting in Room 4, you will reach Room 1 after traversing two passages: (4) \to 2 \to 1. This is the minimum number of passages possible.

Thus, the objective is satisfied.

Sample Input 2

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

Sample Output 2

Yes
6
5
5
1
1

If there are multiple solutions, any of them will be accepted.



Sample input:
4 4
1 2
2 3
3 4
4 2


Sample output:
Yes
1
2
2

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m = inpm()
way = [[] for _ in range(n+1)]
for i in range(m):
    a,b = inpm()
    way[a].append(b)
    way[b].append(a)

ans = [0 for i in range(n+1)]
q = queue.Queue()
q.put((1,0))
while not q.empty():
    room,sign = q.get()
    if ans[room] != 0:
        continue
    ans[room] = sign

    for i in way[room]:
        q.put((i,room))

print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m = inpm()
way = [[] for _ in range(n+1)]
for i in range(m):
    a,b = inpm()
    way[a].append(b)
    way[b].append(a)

ans = [0 for i in range(n+1)]
q = queue.Queue()
q.put((1,0))
while not q.empty():
    room,sign = q.get()
    if ans[room] != 0:
        continue
    ans[room] = sign

    for i in way[room]:
        q.put((i,room))

print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
import networkx as nx
n, m, *AB = map(int, open(0).read().split())
G = nx.Graph()
G.add_nodes_from(range(1, n+1))
G.add_edges_from(zip(AB[::2], AB[1::2]))
print('Yes')
d = dict(nx.bfs_predecessors(G, 1))
for i in range(2, n+1):
    print(d[i])

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

f_inf = float("inf")

n, m = map(int, input().split())
to = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

que = deque([])
que.append(0)

dist = [f_inf for _ in range(n)]
dist[0] = 0

guide = [-1 for _ in range(n)]

while que:
    v = que.popleft()
    for u in to[v]:
        if dist[u] != f_inf: continue
        dist[u] = dist[v]+1
        guide[u] = v
        que.append(u)

print("Yes")
for i in range(1, n):
    ans = guide[i] + 1
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
node=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    node[b-1].append(a-1)
    node[a-1].append(b-1)
distance=[-1]*n
distance[0]=0

d=deque()
d.append(0)
while d:
    v=d.popleft()
    for i in node[v]:
        if distance[i]!=-1:
            continue
        distance[i]=v+1
        d.append(i)
print('Yes')
for i in range(1,n):
    print(distance[i])

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)

INF = 10**10


def search(table, visit):
    d = deque()
    d.append(1)
    while(len(d) > 0):
        next = d.popleft()
        for x in table[next]:
            if visit[x] != INF:
                continue
            visit[x] = next
            d.append(x)


def main(input, print):
    n, m = map(int, input().split())
    table = [[] for _ in range(n+1)]
    visit = [INF]*(n+1)
    for i in range(m):
        a, b = map(int, input().split())
        table[a].append(b)
        table[b].append(a)
    search(table, visit)
    is_ok = True
    for i in range(2, n+1):
        if visit[i] == INF:
            is_ok = False
            break
    if is_ok:
        print('Yes')
        for i in range(2, n+1):
            print(visit[i])
    else:
        print('No')


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
ARR = []

for i in range(M):
    ARR.append(list(map(int, input().split())))


def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStatus = [False for i in range(n)]
    for i in range(m):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1

        nodes[startNode].append(endNode)
        nodes[endNode].append(startNode)

    return nodes, nodeStatus


def calculate(n, nodes, nodeStatus):
    nodeMarks = [-1 for i in range(n)]

    q = deque()

    q.append((0, -1))

    while len(q) > 0:
        currentNode, parentNode = q.popleft()

        if nodeStatus[currentNode] == True:
            continue

        nodeStatus[currentNode] = True
        nodeMarks[currentNode] = parentNode
        childNodes = nodes[currentNode]

        for childNode in childNodes:
            q.append((childNode, currentNode))

    minusNumber = nodeMarks.count(-1)
    if minusNumber > 1:
        print("No")
        return

    print("Yes")
    for i in range(1, n):
        print(nodeMarks[i] + 1)


nodes, nodeStatus = prepare(N, M, ARR)

calculate(N, nodes, nodeStatus)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
ARR = []

for i in range(M):
    ARR.append(list(map(int, input().split())))


def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStatus = [False for i in range(n)]
    for i in range(m):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1

        nodes[startNode].append(endNode)
        nodes[endNode].append(startNode)

    return nodes, nodeStatus


def calculate(n, nodes, nodeStatus):
    nodeMarks = [-1 for i in range(n)]

    q = deque()

    q.append((0, -1))

    while len(q) > 0:
        currentNode, parentNode = q.popleft()

        if nodeStatus[currentNode] == True:
            continue

        nodeStatus[currentNode] = True
        nodeMarks[currentNode] = parentNode
        childNodes = nodes[currentNode]

        for childNode in childNodes:
            if nodeStatus[childNode] == True:
                continue
            q.append((childNode, currentNode))

    minusNumber = nodeMarks.count(-1)
    if minusNumber > 1:
        print("No")
        return

    print("Yes")
    for i in range(1, n):
        print(nodeMarks[i] + 1)


nodes, nodeStatus = prepare(N, M, ARR)

calculate(N, nodes, nodeStatus)

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
import itertools
import collections


# 持っているビスケットを叩き、1枚増やす
# ビスケット A枚を 1円に交換する
# 1円をビスケット B枚に交換する
def main():
    n, m = input_list()
    rooms = []
    for _ in range(m):
        rooms.append(input_list())
    prev = [0]*n
    to_list = [[] for i in range(n)]
    for a, b in rooms:
        to_list[a-1].append(b-1)
        to_list[b-1].append(a-1)
    next_q = collections.deque()
    flags = [-1] * n
    flags[0] = 999
    next_q.append(0)
    while next_q:
        cur = next_q.popleft()
        for room in to_list[cur]:
            if flags[room] == -1:
                flags[room] = cur
                next_q.append(room)
    print('Yes')
    for i in range(1, n):
        print(flags[i]+1)


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
print("Yes")

N,M=map(int,input().split())
lst=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    lst[a-1].append(b-1)
    lst[b-1].append(a-1)
q=deque(lst[0])
go=[None]*N
for i in lst[0]:
    go[i]=0
while q:
    v=q.popleft()
    for new in lst[v]:
        if go[new]==None:
            go[new]=v
            q.append(new)
for i in go[1:]:
    print(i+1)

Submission status: Accepted

Solution code:
from collections import deque
n,m = list(map(int,input().split()))
graph = [[] for _ in range(n+1)]
for i in range(m):
    a, b = list(map(int,input().split()))
    graph[a].append(b)
    graph[b].append(a)
# print(graph)
arrow = [-1]*(n+1)
d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if arrow[i]!=-1:
            continue
        arrow[i] = v
        d.append(i)
    # print(dist)

print('Yes')
print(*arrow[2:], sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
table = []
for i in range(N):
    table.append([])
for i in range(M):
    Ai, Bi = map(int, input().split())
    table[Ai - 1].append(Bi - 1)
    table[Bi - 1].append(Ai - 1)

cost = [1000000] * N
queue = [0]
counter = 0
cost[0] = 0
answer = [-1] * N
answer[0] = 0
while counter < len(queue):
    current = queue[counter]
    counter += 1

    for n in table[current]:
        if cost[current] + 1 < cost[n]:
            cost[n] = cost[current] + 1
            answer[n] = current
            queue.append(n)
print('Yes')
for a in map(lambda x: x + 1, answer[1:]):
    print(a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m = map(int, input().split())
graph = [0] + [[] for _ in range(n)]
for _ in range(m):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

from collections import deque

def bfs(graph, queue, dist, prev):
    while queue:
        current = queue.popleft()

        for c in graph[current]:
            if dist[c] != -1:
                continue
            else:
                dist[c] = dist[current] + 1
                prev[c] = current
                queue.append(c)

queue = deque([1])
dist = [0] + [-1] * n
prev = [0] + [-1] * n
dist[1] = 0
prev[1] = 0
bfs(graph, queue, dist, prev)

if -1 in prev:
    print('No')
else:
    print('Yes')
    for v in prev[2:]:
        print(v)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

neighbor_list = [[] for _ in range(N+1)]
for ab in AB:
    neighbor_list[ab[0]].append(ab[1])
    neighbor_list[ab[1]].append(ab[0])


parent_array = [-1]*(N+1)
parent_array[1] = 0
d = deque([1])
while len(d)!=0:
    v = d.popleft()
    for ch in neighbor_list[v]:
        if parent_array[ch] == -1:
            parent_array[ch] = v
            d.append(ch)

print('Yes')
for i in parent_array[2:]:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
links = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].append(b)
    links[b].append(a)

ans = [-1] * n
ans[0] = 0
q = deque([(0, 0)])
while q:
    room, prev = q.popleft()
    for next_ in links[room]:
        if ans[next_] < 0:
            ans[next_] = room
            q.append((next_, room))

print('Yes')
for i in range(1, n):
    print(ans[i] + 1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m = map(int, readline().split())

# グラフを作成(隣接リスト表現)
graph = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)

# distance
dist = [-1] * (n + 1)
point = [-1] * (n + 1)
dist[0] = 0
dist[1] = 0
point[0] = 0
point[1] = 0

q = deque([])
q.append(1)

while len(q) > 0:
    v = q.popleft()
    # キューから先頭頂点(調べる点）を取り出す

    # v から辿れる頂点をすべて調べる
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        point[i] = v
        q.append(i)

if - 1 not in set(point):
    print('Yes')
    for k in point[2::]:
        print(k)
else:
    print('No')

Submission status: Accepted

Solution code:
#import time
from itertools import dropwhile, takewhile
def main():
    N, M = list(map(int, input().split()))
    lis = [list(map(int, input().split())) for _ in range(M)]
    #print(lis)
    edge = [[] for _ in range(N+1)]
    #print(edge)
    for a,b in lis:
        edge[a].append(b)
        edge[b].append(a)
        #print(edge)
    ans = [0] * (N+1)
    visited = {0}
    stack = [1]
    for i in stack:
        for j in edge[i]:
            if j in visited:
                continue
            stack.append(j)
            #print(stack)
            visited.add(j)
            #print(visited)
            ans[j]=i
    print("Yes")
    for k in ans[2:]:
        print(k)


if __name__ == '__main__':
    #start = time.time()
    main()
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)

ans = [-1] * n
from collections import deque
d = deque([0])
while d:
    u = d.popleft()
    for v in G[u]:
        if ans[v] == -1:
            ans[v] = u
            d.append(v)

if -1 in ans[1:]:
    print('No')
else:
    print('Yes')
    for v in ans[1:]:
        print(v + 1)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
neighbors = {key:[] for key in range(1, n+1)}
answers = {key:0 for key in range(1, n+1)}
answers[1] = 1
for i in range(m):
    a,b = map(int, input().split())
    neighbors[a].append(b)
    neighbors[b].append(a)

def register(hs):
    newhs = []
    for h in hs:
        for i in neighbors[h]:
            if answers[i] == 0:
                answers[i] = h
                newhs.append(i)
    return newhs

hosts = [1]
while True:
    hosts = register(hosts)
    if len(hosts) == 0:
        break

flag = 0
for key, item in answers.items():
    if item == 0:
        flag = 1
if flag == 0:
    print("Yes")
    for key, item in answers.items():
        if key != 1:
            print(item)
else:
    print("No")

Submission status: Accepted

Solution code:
def dijkstra(v, G):
    import heapq

    ret = [10 ** 10] * len(G)
    ret[v] = 0
    q = [(ret[i], i) for i in range(len(G))]
    heapq.heapify(q)

    while len(q):
        tmpr, u = heapq.heappop(q)
        if tmpr == ret[u]:
            for w in G[u]:
                if ret[w] > ret[u] + 1:
                    ret[w] = ret[u] + 1
                    heapq.heappush(q, (ret[w], w))
    return ret


N, M = map(int, input().split())
G, ans = {i: [] for i in range(N)}, [-1] * N
for _ in range(M):
    A, B = map(int, input().split())
    G[A - 1].append(B - 1)
    G[B - 1].append(A - 1)

d = dijkstra(0, G)
for a in range(N):
    for b in G[a]:
        if d[a] - d[b] == 1:
            ans[a] = b + 1

print("Yes")
for a in ans[1:]:
    print(a)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
adj=[[] for _ in range(n)]
for _ in range(m):
  a,b =map(int,input().split())
  a-=1
  b-=1
  adj[a].append(b)
  adj[b].append(a)
ans=[0]*n
que=deque([])
que.append(0)
while que:
  e=que.popleft()
  for i in adj[e]:
    if ans[i]!=0:
      continue
    ans[i]=e+1
    que.append(i)
print("Yes")
for i in range(1,n):
  print(ans[i])

Submission status: Accepted

Solution code:
n,M = list(map(int,input().split()))

m = [[] for _ in range(n)]
dp = [0]*n
from collections import deque
que = deque()
for _ in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  m[a].append(b)
  m[b].append(a)
  if a == 0:
    que.append(b)
    dp[b] = 1
  if b == 0:
    que.append(a)
    dp[a] = 1

while que:
  c = que.popleft()
  for i in m[c]:
    if dp[i] == 0 :
      dp[i] = c+1
      que.append(i)

#[exit(print('No')) for i in range(1,n)  if dp[i] == 0]

print('Yes')
[print(dp[i]) for i in range(1,n)]

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
a = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    a[x - 1].append(y - 1)
    a[y - 1].append(x - 1)
c = [0] * n
que = deque([])
que.append(0)
while len(que) > 0:
    e = que.popleft()
    for i in a[e]:
        if c[i] > 0:
            continue
        c[i] = e + 1
        que.append(i)
print("Yes")
for i in range(1, n):
    print(c[i])

Submission status: Accepted

Solution code:
#D
from collections import deque
n, m = map(int, input().split())
ans = [0] * (n+1)
g = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
#BPS幅優先探索を行う -> 前の座標を記入
nque = deque([1])
while nque:
    now_cave = nque.popleft()
    for next_cave in g[now_cave]:
        if ans[next_cave] == 0:
            ans[next_cave] = now_cave
            nque.append(next_cave)
#         print(nque)
# print(ans)
print("Yes")
for i in range(2, n + 1):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dist = [[-1,0] for _ in range(n+1)]
dist[0][0] = 0
dist[1][0] = 0

d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i][0] != -1:
            continue
        dist[i][0] = dist[v][0] + 1
        dist[i][1] = v
        d.append(i)

ans = dist[2:]

print('Yes')
for j in range(n-1):
    print(ans[j][1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
nextroom = [[] for _ in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  nextroom[A-1].append(B-1)
  nextroom[B-1].append(A-1)

sgn = [-1 for _ in range(N)]
sgn[0] = 0

depth = [float('inf') for _ in range(N)]
depth[0] = 0

now = [0]
nextvisit = []
for j in range(1, M+1):
  for n in now:
    for i in nextroom[n]: 
      if depth[i] > j:
        nextvisit.append(i)
        sgn[i] = n
        depth[i] = j
  now = [] + nextvisit
  nextvisit = []

if -1 in sgn:
  print('No')
else:
  print('Yes')
  for k in range(1, len(sgn)):
    print(sgn[k]+1)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
g = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    g[A-1].append(B)
    g[B-1].append(A)

ans = [-1] * N
ans[0] = 0
d = deque([1])
while len(d) != 0:
    now = d[0]
    d.popleft()
    for i in g[now-1]:
        if ans[i-1] != -1:
            continue
        ans[i-1] = now
        d.append(i)

if -1 in ans:
    print('No')
else:
    print('Yes')
    for i in ans[1:]:
        print(i)

Submission status: Accepted

Solution code:
from collections import deque

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

# N個の空の配列
# g[0]は空のまま
path_list = [[] for i in range(N + 1)]

# 繋がっている部屋をメモ
for i in range(M):
    a, b = list(map(int, input().split()))
    path_list[a].append(b)
    path_list[b].append(a)

queue = deque([1])
d = [None] * (N + 1)

while queue:
    # popleft()で先頭の要素を返しつつ削除
    v = queue.popleft()
    # vから行ける全ての部屋について
    for i in path_list[v]:
        if d[i] is None:
            d[i] = v
            queue.append(i)

print("Yes")
# 2番以降の部屋について
for i in d[2:]:
    print(i)

Submission status: Accepted

Solution code:
inlist=input("").split(" ")
n=int(inlist[0])
m=int(inlist[1])
lista=[]
listb=[]
for i in range(n):
    lista+=[[]]
    listb+=[-1]
listb[0]=-2

listnum=[0]
for i in range(m):
    inlist=input("").split(" ")
    s=int(inlist[0])
    t=int(inlist[1])
    lista[s-1]+=[t-1]
    lista[t-1]+=[s-1]
k=0
while(k<len(listnum)):
    for i in lista[listnum[k]]:
        
        if(listb[i]==-1):
            listb[i]=listnum[k]
            listnum+=[i]
    k+=1

if (-1 in listb):
    print("No")
else:
    print("Yes")
    for i in listb[1:]:
        print(i+1)

Submission status: Accepted

Solution code:
import queue
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
q = queue.Queue()
q.put(0)
d = [-1]*n
d[0] = 0

while not q.empty():
    v = q.get()
    for i in g[v]:
        if d[i] != -1:
            continue
        d[i] = v
        q.put(i)
if -1 in d:
    print("No")
else:
    print("Yes")
    for i in d[1:]:
        print(i+1)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

n,m = I()
g = [[] for _ in range(n)]
for i in range(m):
    a,b = I()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
q = deque([0])
d = [-1]*n
d[0] = 0
while q:
    v = q.popleft()
    for i in g[v]:
        if d[i] != -1:
            continue
        d[i] = v
        q.append(i)
if -1 in d:
    print("No")
else:
    print("Yes")
    for i in d[1:]:
        print(i+1)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
q = deque([0])
d = [-1]*n
d[0] = 0
while q:
    v = q.popleft()
    for i in g[v]:
        if d[i] != -1:
            continue
        d[i] = v
        q.append(i)
if -1 in d:
    print("No")
else:
    print("Yes")
    for i in d[1:]:
        print(i+1)

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
 
g=[[] for i in range(N+1)]
 
for i in range(M):
	a,b=list(map(int,input().split()))
	g[a].append(b)
	g[b].append(a)
 
from collections import deque
 
queue = deque([1])
d = [None] * (N+1)
while queue:
	v = queue.popleft()
	for i in g[v]:
		if d[i] is None:
			d[i] = v
			queue.append(i)
 
print("Yes")
print(*d[2:],sep='\n')

Submission status: Accepted

Solution code:
from collections import deque

def bfs(graph, visited, ss):
  queue = deque([ss])
  visited[ss] = 0
  ans = [0]*n
  while queue:
    s = queue.popleft()
    for new_s in graph[s] :
      if visited[new_s] == -1:
        #　移動回数の計算
        visited[new_s] = visited[s] + 1
        queue.append(new_s)
        ans[new_s] = s
  return ans

n,m = map(int,input().split())
graph = [[] for j in range(n)]

for i in range(m):
    a,b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

visited = [-1]*n
ans = bfs(graph, visited, 0)

print('Yes')
for i in range(1,n) :
  print(ans[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

n, m = [int(w) for w in input().split()]
links = [[] for i in range(n + 1)]
mark = [-1] * (n + 1)

for i in range(m):
    a, b = [int(w) for w in input().split()]
    links[a].append(b)
    links[b].append(a)

q = deque([1])
while q:
    now = q.popleft()
    for l in links[now]:
        if mark[l] == -1:
            q.append(l)
            mark[l] = now

if -1 in mark[2:]:
    print("No")
else:
    print("Yes")
    print("\n".join([str(w) for w in mark[2:]]))

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
N, M = map(int, input().split())
edges = defaultdict(list)
ans = [0]*(N+1)
num = 1
q = deque([1])
currentdepth = {1}
nextdepth = set()
for _ in range(M):
  a, b = map(int, input().split())
  edges[a].append(b)
  edges[b].append(a)
while q:
  current = q.popleft()
  for nextver in edges[current]:
    if ans[nextver]==0:
      q.append(nextver)
      ans[nextver] = current
print('Yes')
print(*(ans[2:]),sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
n,m  = map(int, input().split())
r = [[] for _ in range(n+1)]
ans = [0]*(n+1)
for i in range(m):
  a,b  = map(int, input().split())
  r[a].append(b)
  r[b].append(a)

q = deque([1])
while q:
  fr = q.popleft()
  for i in r[fr]:
    if ans[i] != 0:
      continue
    ans[i] = fr
    q.append(i)
print("Yes")
for i in ans[2:]:
  print(i)

Submission status: Accepted

Solution code:
def main():
    n, m = (int(i) for i in input().split())
    graph = { i: [] for i in range(1, n+1) }

    for i in range(m):
        src, dst = (int(i) for i in input().split())
        graph[src].append(dst)
        graph[dst].append(src)

    def bfs():
        st = [1] 
        pptr = { 1: 0 }

        while st:
            room = st.pop(0)
            for dest_room in graph[room]:
                if dest_room in pptr:
                    continue
                st.append(dest_room)
                pptr[dest_room] = room

        return pptr

    pptr = bfs()
    if len(pptr) != n:
        print('No')

    else:
        print('Yes')
        for i in sorted(pptr.keys()):
            if i == 1:
                continue
            print(pptr[i])

main()

Submission status: Accepted

Solution code:
# 幅優先探索
from collections import deque

N, M = map(int, input().split())
AB = [map(int, input().split()) for _ in range(M)]

links = [[] for _ in range(N + 1)]
for a, b in AB:
    links[a].append(b)
    links[b].append(a)

result = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print('Yes')
print(*result[2:], sep='\n')

Submission status: Accepted

Solution code:
# 幅優先探索
from collections import deque

N, M = map(int, input().split())
AB = [map(int, input().split()) for _ in range(M)]

links = [[] for _ in range(N + 1)]
for a, b in AB:
    links[a].append(b)
    links[b].append(a)

result = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print('Yes')
print('\n'.join(str(i) for i in result[2:]))

Submission status: Accepted

Solution code:
from collections import deque
def main():
    N,M,*AB=map(int,open(0).read().split())
    g=[[] for _ in range(N+1)]
    for a,b in zip(*[iter(AB)]*2):
        g[a].append(b)
        g[b].append(a)
    q=deque([1])
    s=[0]*(N+1)
    s[1]=1
    while q:
        u=q.popleft()
        for v in g[u]:
            if not s[v]:
                s[v] = u
                q.append(v)
    print("Yes")
    print("\n".join(map(str, s[2:])))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())

graph = [[] for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    
#部屋から1までの距離(深さ)
dist = [-100 for _ in range(n)]
dist[0] = 0

#幅優先探索でdistを更新
#pに今いる位置を格納
p = deque()
p.append(0)

while len(p) > 0:
    now = p.pop()
    for i in graph[now]:
        if dist[i] != -100:
            continue
        p.appendleft(i)
        dist[i] = now
        
print('Yes')
for i in range(1,n):
    print(dist[i]+1)