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:
from collections import deque
N,M = map(int,input().split())
cnct = [[] for i in range(N+1)]
for _ in range(M):
  A,B = map(int,input().split())
  cnct[A].append(B)
  cnct[B].append(A)
Q = deque()
Q.append(1)
ans = [0]*(N+1)
vstd = [0]*(N+1)
while Q:
  temp = Q.popleft()
  for a in cnct[temp]:
    if vstd[a] == 0:
      ans[a] = temp
      vstd[a] = 1
      Q.append(a)
print('Yes')
for a in ans[2:]:
  print(a)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
cnct = [[] for i in range(N+1)]
for _ in range(M):
  A,B = map(int,input().split())
  cnct[A].append(B)
  cnct[B].append(A)
Q = deque()
Q.append(1)
ans = [0]*(N+1)
vstd = [0]*(N+1)
# ans[1]を出力しない以上、vstd[1]=1にしておく必要はない
#（vstd[1]=0のままなら、ans[1]に余計な道しるべが追加されるだけ）
while Q:
  temp = Q.popleft()
  for a in cnct[temp]:
    if vstd[a] == 0:
      ans[a] = temp
      vstd[a] = 1
      Q.append(a)
print('Yes')
for a in ans[2:]:
  print(a)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
ab=[[] for i in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  ab[a].append(b)
  ab[b].append(a)
ans=[-1]*(N+1)
que=deque([1])
while que:
  q=que.popleft()
  for i in ab[q]:
    if ans[i]==-1:
      que.append(i)
      ans[i]=q
print('Yes')
for i in range(2,N+1):
  print(ans[i])

Submission status: Accepted

Solution code:
import queue
n,m = map(int,input().split())
way = [set() for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    way[a-1].add(b-1)
    way[b-1].add(a-1)
    
guide = [-1]*n
guide[0] = 0
q = queue.Queue() #[room_number,cost]
q.put((0,0))
while not q.empty():
    room,cost = q.get()
    for k in way[room]: #roomと道が繋がっている部屋を列挙
        if guide[k] == -1:
            guide[k] = room
            q.put((k,cost+1))
            way[k].discard(room)
            
if -1 in guide:
    print('No')
else:
    print('Yes')
    for i in guide[1:]:
        print(i+1)

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)
par = [0]*(n+1)
visited = [0]*(n+1)
root = 1
visited[root] = 1
q = deque([root])
while q:
  v = q.popleft()
  for w in links[v]:
    if visited[w]:
      continue
    visited[w] = 1
    par[w] = v
    q.append(w)
    
print('Yes')
print(*par[2:], sep='\n')

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def BFS(n,m,table,dist):
    next = deque([0])
    while next:
        tmp = next.popleft()
        for rep in table[tmp]:
            if dist[rep]==-1:
                dist[rep] = tmp+1
                next.append(rep)
    return not -1 in dist

def main():
    n,m = IL()
    table = [[] for _ in range(n)]
    for _ in range(m):
        a,b = IL()
        table[a-1].append(b-1)
        table[b-1].append(a-1)
    dist = [-1]*n
    dist[0] = 0
    if BFS(n,m,table,dist):
        print('Yes')
        for i in range(1,len(dist)):
            print(dist[i])
    else:  print('No')
    return

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
import numpy as np

N, M = [int(x) for x in input().split(" ")]

e = {i: [] for i in range(N)}
for _ in range(M):
  a, b = [int(x)-1 for x in input().split(" ")]
  e[a].append(b)
  e[b].append(a)

d = np.ones(N, dtype=int) * -1
q = [0]
while len(q) != 0:
  v = q.pop(0)
  for ne in e[v]:
    if d[ne] == -1:
      d[ne] = v
      q.append(ne)

print("Yes")
# for p in prev[1:]:
#   print(p+1)
# print("\n".join([str(p+1) for p in d[1:]]))
for p in d[1:]:
  print(p+1)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split(" "))

goto = {i: [] for i in range(1, N+1)}
sign = np.zeros(N, dtype=int)
for _ in range(M):
  A, B = map(int, input().split(" "))
  goto[A].append(B)
  goto[B].append(A)

# print(goto)

visited = set([1])
queue = [1]
while len(queue) > 0:
  v = queue.pop(0)
  for nex in goto[v]:
    if nex in visited:
      continue
    sign[nex-1] = v
    queue.append(nex)
    visited.add(nex)
print("Yes")
for s in sign[1:]:
  print(s)

Submission status: Accepted

Solution code:
from collections import deque

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

adj = [[] for i in range(n+1)]
dist = [-1]*(n+1)

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

d = deque([[1,0]])

while len(d) > 0:
    x,y = d.popleft()
    if dist[x] != -1:
        continue
    
    dist[x] = y
    
    for n in adj[x]:
        if dist[n] == -1:
            d.append([n,x])

print("Yes")

for i in dist[2:]:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
d = {i:[] for i in range(1, N+1)}

for _ in range(M):
    A, B = map(int, input().split())
    d[A].append(B)
    d[B].append(A)

q = deque([1])
INF = 10**20
dist = [INF]*(N+1)
dist[1] = 0
par = [-1]*(N+1)
par[1] = 0

while q:
    a = q.popleft()
    for b in d[a]:
        if dist[b] > dist[a]+1:
            dist[b] = dist[a]+1
            par[b] = a
            q.append(b)

print("Yes")
for i in range(2, N+1):
    print(par[i])

Submission status: Accepted

Solution code:
# D - .. (Double Dots)
from collections import deque

N,M = map(int,input().split())
route = [deque([]) for _ in range(N+1)]
for _ in range(M):
    A,B = map(int,input().split())
    route[A].append(B)
    route[B].append(A)
    
ans = [0]*2+[-1]*(N-1)
que = deque([1])

while len(que)>0:
    k = que.popleft()
    for x in route[k]:
        if ans[x]<0:
            ans[x] = k
            que.append(x)

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

Submission status: Accepted

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

done=[False for i in range(n)]
ans=[-1 for i in range(n)]
def bfs():
  que=[0]

  while(que):
    now=que.pop(0)
    done[now]=True
    for i in l[now]:
      if done[i]==False:
        que.append(i)
        done[i]=True
        ans[i]=now+1
bfs()
print("Yes")
print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
A=[set() for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  A[a-1].add(b)
  A[b-1].add(a)
visit=[0]*n
visit[0]=n+1
stack=deque()
stack.append(1)
while stack:
  now=stack.popleft()
  for j in A[now-1]:
    if visit[j-1]==0:
      visit[j-1]=now
      stack.append(j)
if min(visit)>0:
  print('Yes')
  for j in range(1,n):
    print(visit[j])
else:
  print('No')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 14 16:45:05 2020

@author: NEC-PCuser
"""

from collections import deque

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

g = [[] for _ in range(N)] # 隣接リスト

for i in range(M):
    a_tmp, b_tmp = map(int, input().split())
    g[a_tmp - 1].append(b_tmp - 1)
    g[b_tmp - 1].append(a_tmp - 1)
    
queue = deque([0])

d = [-1] * N
d[0] = 0

while queue:
    v = queue.popleft()
    for i in g[v]:
        if d[i] == -1:
            d[i] = v
            queue.append(i)

out_flg = True
for i in d:
    if i == -1:
        out_flg = False
        break

if out_flg is False:
    print("No")
else:
    print("Yes")
    for i in range(1, len(d)):
        print(d[i] + 1)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
edge=[[] for i in range(N)]
visited=[-1 for i in range(N)]
dist=[1000000000 for i in range(N)]
last=[-1 for i in range(N)]
i=0
dist[0]=0
for i in range(M):
    A,B=map(int,input().split())
    edge[A-1].append(B-1)
    edge[B-1].append(A-1)
Q=deque()
Q.append(0)
while Q:
    i=Q.popleft()
    if visited[i]==-1:
        for j in edge[i]:
            if dist[j]>dist[i]+1:
                dist[j]=dist[i]+1
                last[j]=i+1
            if visited[j]==-1:
                Q.append(j)
    visited[i]=1
print("Yes")
for i in range(1,N):
	print(last[i])

Submission status: Accepted

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

target = [[] for i in range(n)]

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

queue = [0]
isSearched = [False]*n
isSearched[0] = True
ans = [-1]*n
def bfs():
    while(queue):
        now = queue.pop(0)

        for t in target[now]:
            if(isSearched[t]):
                continue
            ans[t] = now
            queue.append(t)
            isSearched[t] = True
bfs()
print('Yes')
for i in range(n):
    if(i==0):
        continue
    print(ans[i]+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 168: D - .. (Double Dots)
https://atcoder.jp/contests/abc168/tasks/abc168_d
"""


def main():
    N, M = map(int, input().split())

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

    dist = [-1]*N
    q = [0]
    while q:
        v = q.pop(0)
        for i in to[v]:
            if dist[i] != -1:
                continue
            dist[i] = v
            q.append(i)

    print('Yes')
    for i in range(1, N):
        print(dist[i]+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 168: D - .. (Double Dots)
https://atcoder.jp/contests/abc168/tasks/abc168_d
"""


def main():
    N, M = map(int, input().split())

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

    p = [-1]*N
    q = [0]
    while q:
        v = q.pop(0)
        for u in to[v]:
            if p[u] == -1:
                p[u] = v
                q.append(u)
    print('Yes')
    for i in range(1, N):
        print(p[i]+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
N, M = map(int, input().split())
G = [[] for i in range(N)]
R = [0]*N
for m in range(M):
    A,B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
d = deque()
for n in G[0]:
    d.append(n)
    R[n]=1
while len(d)>0:
    i = d.popleft()
    for j in range(len(G[i])):
        if R[G[i][j]] == 0 and G[i][j]!=0:
            d.append(G[i][j])
            R[G[i][j]]=i+1
for n in range(1,N):
    if R[n]==0:
        print("No")
        sys.exit()
print("Yes")
for n in range(1,N):
    print(R[n])

Submission status: Accepted

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

lab = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    lab[a].append(b)
    lab[b].append(a)

l = [0]*(n+1)
num = [1]

while num:
    v = num.pop(0)
    for i in lab[v]:
        if not l[i]:
            l[i] = v
            num.append(i)
            
if not 0 in l[2:]:
    print("Yes")
    for i in range(2, n+1):
        print(l[i])
else:
    print("No")

Submission status: Accepted

Solution code:
#import copy
from collections import deque


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


n, m = xnxn()
a = xnxn(m)

graph = [[] for _ in range(n+1)]
for g in a:
    graph[g[0]].append(g[1])
    graph[g[1]].append(g[0])

# print(graph)

d = deque([1])
rout = [0]*(n+1)
while d != deque([]):
    pos = d.popleft()
    for i in graph[pos]:
        if rout[i] == 0:
            rout[i] = pos
            d.append(i)


if rout != [0]*(n+1):
    print("Yes")
    for i in rout[2:]:
        print(i)
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000)
n,m=map(int,input().split())
path={i:[] for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  path[a-1].append(b)
  path[b-1].append(a)
sign=[0]*n

def bfs(poslist,sign):
  if len(poslist)==0:
    return sign
  nex=[]
  for pos in poslist:
    lis = [x for x in path[pos-1] if sign[x-1]==0]
    for i in lis:
      sign[i-1]=pos
      nex.append(i)
  return bfs(nex,sign)
      
  
sign=bfs([1],sign)
print('Yes')
for i in range(1,n):
  print(sign[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

from collections import deque

class Node:
    def __init__(self, id_=0):
        self.id = id_
        self.link = []
        self.check = False

def main():
    N, M = map(int, input().split())

    nodes = [Node(i) for i in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        nodes[a].link.append(nodes[b])
        nodes[b].link.append(nodes[a])
    
    pre = [-1] * N
    q = deque()
    q.append(nodes[0])
    nodes[0].check = True
    while len(q) > 0:
        node = q.popleft()
        for nex in node.link:
            if not nex.check:
                nex.check = True
                pre[nex.id] = node.id
                q.append(nex)
    
    print("Yes")
    for i in range(1, N):
        print(pre[i]+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i:[] for i in range(n)}
for i in range(m):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

que = deque([0])
res = {0:-1}
while len(que) > 0:
    cur = que.popleft()
    for _next in graph[cur]:
        if _next in res:
            continue
        res[_next] = cur
        que.append(_next)

if len(res) < n:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(res[i]+1)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
graph=[[] for i in range(N)]
for m in range(M):
    A,B=map(int,input().split())
    graph[A-1].append(B-1)
    graph[B-1].append(A-1)
queue=deque([0])
distance=[0]*N
while queue:
    room=queue.popleft()
    for next_room in graph[room]:
        if distance[next_room]==0:
            distance[next_room]=room+1
            queue.append(next_room)
if 0 in distance:
    print("No")
else:
    print("Yes")
    print(*distance[1:],sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(m):
  a,b = map(int, input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)
  
depth = [-1] * n
prev = [-1] * n

q = deque([0])
depth[0] = 0

while len(q) > 0:
  pos = q.popleft()
  for i in tree[pos]:
    if depth[i] == -1:
      depth[i] = depth[pos] + 1
      prev[i] = pos
      q.append(i)
      
print('Yes')
for i in range(1,n):
  ans = prev[i] + 1
  print(ans)

Submission status: Accepted

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

to = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
print('Yes')
q = deque([])
dist = [INF] * n
pre = [-1] * n
dist[0] = 0
q.append(0)

while len(q) > 0:
    v = q.popleft()
    for i in to[v]:
        if dist[i] != INF:
            continue
        dist[i] = dist[v] + 1
        pre[i] = v
        q.append(i)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
adj = {}
for i in range(N):
    adj[i + 1] = []
for i in range(M):
    v1, v2 = map(int, input().split())
    adj[v1].append(v2)
    adj[v2].append(v1)

visited = {1}
parent = {1: None}
frontier = [1]
while frontier:
    nxt = []
    for u in frontier:
        for v in adj[u]:
            if v not in visited:
                parent[v] = u
                nxt.append(v)
                visited.add(v)
    frontier = nxt

if len(visited) < N:
    print("No")
else:
    print("Yes")
    for i in range(2, N + 1):
        print(parent[i])

Submission status: Accepted

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

from collections import deque

q = deque()

prev = [-1] * n

q.append(0)
while q:
    v = q.popleft()
    for e in edges[v]:
        if prev[e] != -1:
            continue
        prev[e] = v
        q.append(e)

print("Yes")
for val in prev[1:]:
    print(val + 1)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
graph=[[] for i 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)
queue=deque([0])
distance=[0]*N
while queue:
    que=queue.popleft()
    for value in graph[que]:
        if distance[value]==0:
            distance[value]=que+1
            queue.append(value)
if 0 in distance:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(distance[i])

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
graph=[[] for i 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)
queue=deque([0])
distance=[0]*N
while queue:
    value=queue.popleft()
    for i in graph[value]:
        if distance[i]<1:
            distance[i]=value+1
            queue.append(i)
if 0 in distance:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(distance[i])

Submission status: Accepted

Solution code:
from collections import deque

N, M = [int(i) for i in input().split()]

graph = { _:[] for _ in range(N)}

for _ in range(M):
    a, b = [int(i) for i in input().split()]
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    
visited = [0] * N

que = deque([0])

while que:
    v = que.popleft()
    for i in graph[v]:
        if visited[i] < 1:
            visited[i]+=v+1
            que.append(i)
            
if 0 in visited:
    print('No')
else :
    print('Yes')
    for v in visited[1:]:
        print(v)

Submission status: Accepted

Solution code:
#

import sys
from collections import deque
input=sys.stdin.readline

def main():
    N,M=map(int,input().split())
    adj=[[] for i in range(N)]
    for i in range(M):
        A,B=map(int,input().split())
        adj[A-1]+=[B-1]
        adj[B-1]+=[A-1]
    parent=[-1]*N
    qu=deque([0])
    qup=qu.popleft
    qua=qu.append
    parent[0]=0
    while(len(qu)>0):
        v=qup()
        for nv in adj[v]:
            if parent[nv]!=-1:
                continue
            else:
                parent[nv]=v
                qua(nv)
    print("Yes")
    for i in range(1,N):
        print(parent[i]+1)
        
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

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

x = [[] for i in range(n+1)]

for i in range(m):
    x1, y1 = [int(i) for i in input().split()]
    x[x1].append(y1)
    x[y1].append(x1)

ans = [10**10] * n
ans[0] = 0
root = [10**10] * n
root[0] = 0

from collections import deque
q = deque() # FIFOキューの作成
for i in x[1]:
    q.append((1,i))#現在の深さ、次に行ける所
    root[i-1] = 1

while q:
    a,b = q.popleft() #aが現在の位置　bが次に行く所
    #ここを簡略化したい
    if (ans[a-1] + 1) < ans[b-1]:
        root[b-1] = a
        ans[b - 1] = ans[a - 1] + 1
    else:
        continue

    for i in x[b]:
        if ans[i-1] > (ans[a-1]+1):
            q.append((b,i))


for i in ans[1:]:
    if i == 10**10:
        print("No")
        exit()

print("Yes")
[print(i) for i in root[1:]]

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)

p=[0]*N
que= deque([0])

while que:
    v=que.popleft()
    for i in graph[v]:
        if p[i]<1:
            p[i]=v+1
            que.append(i)

if 0 in p:
    print("No")
else:
    print("Yes", *p[1:], sep="\n")

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
G=[]
for i in range(0,N):
    G.append([])

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

q=[]
sign=[-1]*N
sign[0]=0
q.append(0)
while q:
    x=q.pop(0)
    for nv in G[x]:
        if sign[nv]==-1:
            sign[nv]=x
            q.append(nv)

print("Yes")
for i in range(1,N):
    print(sign[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n, m = map(int, input().split())
    to = [[] for _ in range(n+1)]
    ans = [None]*(n+1)
    for _ in range(m):
        a, b = map(int, input().split())
        to[a].append(b)
        to[b].append(a)
    q = deque([1])
    while q:
        p = q.pop()
        children = to[p]
        for child in children:
            if ans[child] is None:
                ans[child] = p
                q.appendleft(child)
    print("Yes")
    print("\n".join(list(map(str, ans[2:]))))
            
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in g[i]:
        if ans[j] == -1:
            ans[j] = i
            q.append(j)
print('Yes')
for i in ans[2:]:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n, m = map(int, input().split())
    to = [[] for _ in range(n+1)]
    ans = [None]*(n+1)
    for _ in range(m):
        a, b = map(int, input().split())
        to[a].append(b)
        to[b].append(a)
    q = deque([1])
    while q:
        p = q.pop()
        for child in to[p]:
            if ans[child] is None:
                ans[child] = p
                q.appendleft(child)
    print("Yes")
    for a in ans[2:]:
        print(a)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def resolve():
    n, m = map(int, input().split())
    adj = [[] for i in range(n+1)]
    for i in range(m):
        A, B = map(int, input().split())
        adj[A].append(B)
        adj[B].append(A)
    from collections import deque
    q = deque([1])
    ans = [-1 for i in range(n+1)]
    while q:
        v = q.popleft()
        for u in adj[v]:
            if ans[u] == -1:
                ans[u] = v
                q.append(u)
    print("Yes")
    for i in range(2, n+1):
        print(ans[i])

resolve()

Submission status: Accepted

Solution code:
from collections import deque


N, M = [int(i) for i in input().split()]
gp = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(i) for i in input().split()]
    gp[a-1].append(b-1)
    gp[b-1].append(a-1)

signs = [-1] * N
que = deque()
que.append((-2, 0))
seen = set()
while(que):
    fr, de = que.popleft()
    if(de in seen):
        continue
    signs[de] = fr
    seen.add(de)
    for next_de in gp[de]:
        if(next_de not in seen):
            que.append((de, next_de))

if(len(seen) == N):
    print('Yes')
    for s in signs[1:]:
        print(s+1)
else:
    print('No')

Submission status: Accepted

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

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

d = deque([0])
ans = [-1]*n
ans[0]=0
while d:
  p=d.popleft()
  for v in r[p]:
    if ans[v]!=-1: continue
    ans[v]=p
    d.append(v)
if -1 in ans:
  print('No')
  exit()
else:
  print('Yes')
  for v in ans[1:]:
    print(v+1)

Submission status: Accepted

Solution code:
def resolve():
    n, m = map(int, input().split()) # 標準入力1行目の処理、n頂点、m辺
    adj = [[] for i in range(n+1)] # 隣接リスト初期化、要素数は頂点数
    for i in range(m):
        A, B = map(int, input().split())
        adj[A].append(B) # このappendのやり方だと、adj[0]が空になることに注意
        adj[B].append(A) # （問題文の頂点インデックスが1始まりであるため）
    #print(adj)
    # 隣接リストさえ作成できたら、あとはBFSで全探索するだけ

    from collections import deque
    q = deque([1])
    ans = [-1 for i in range(n+1)]
    while q:
        v = q.popleft() # vertex(頂点)の意
        for u in adj[v]:
            if ans[u] == -1: # 未踏なら
                ans[u] = v
                q.append(u)
    print("Yes")
    for i in range(2, n+1):
        print(ans[i])

resolve()

Submission status: Accepted

Solution code:
(N, M), *miti = [[*map(int, line.split())] for line in open(0)]

# print(miti)

A = [list() for _ in range(N+1)]
for m in miti:
    a, b = m
    A[a].append(b)
    A[b].append(a)

# print(A)

ans = [0] * (N + 1)
dist = [N] * (N + 1)
R = [list() for _ in range(N)]

dist[1] = 0
R[0].append(1)
ans[1] = 88888
for i in range(N):
    for p in R[i]:
        for t in A[p]:
            if i + 1 < dist[t]:
                dist[t] = i + 1
                R[i+1].append(t)
                ans[t] = p

dist = dist[1:]
ans = ans[2:]
if all(d < N for d in dist):
    print("Yes")
    for a in ans:
        print(a)
else:
    print("No")

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)
# 例2のlinksの出力結果
# [[], [6, 5], [4, 6], [4, 5], [3, 2, 6, 5], [3, 1, 4, 6], [1, 4, 2, 5]]
result = [-1] * (N + 1)
# 例2のq出力結果
# deque([1])
# deque([6, 5])リスト1幅優先探索だからより深い方
# deque([5, 1, 4, 2])6を押し出してリスト6を挿入
# deque([1, 4, 2, 3])5を押し出してリスト5から残りの3を挿入
# deque([4, 2, 3])
# deque([2, 3])
# deque([3])
# deque([])
q = deque([1])
# 全部押し出されたら1周
while q:
    # qの先頭を押し出す
    i = q.popleft()
    # 上から順に見ていく
    for j in links[i]:
        # resultのj番目が-1なら次の処理というか基本-1
        # 例えばrsultリストの1が-1ならリスト1の「6,4」の左側6を挿入する
        if result[j] == -1:
            result[j] = i
            # 処理したら右に追加してまた押し出す
            q.append(j)
# result j qの出力結果
# [-1, -1, -1, -1, -1, -1, 1]
# 6
# [-1, -1, -1, -1, -1, 1, 1]
# 5
# [-1, 6, -1, -1, -1, 1, 1]
# 1
# [-1, 6, -1, -1, 6, 1, 1]
# 4
# [-1, 6, 6, -1, 6, 1, 1]
# 2
# [-1, 6, 6, 5, 6, 1, 1]
# 3
print('Yes')
# 開業で文字列として羅列
print('\n'.join(str(i) for i in result[2:]))

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)

#print(graph)

dist = [-1]*2 + [0 for i in range (n-1)]
dist[1] = 0
d = deque([1])
#print(d)

while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] == 0:
            dist[i] = v
            d.append(i)
            #print(i ," " ,dist[i], d)
            

print("Yes")
ans = dist[2:]
print(*ans, sep="\n")

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)

#print(graph)

dist = [-1]*2 + [0 for i in range (n-1)]

d = deque([1])
#print(d)

while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] == 0:
            dist[i] = v
            d.append(i)

print("Yes")
ans = dist[2:]
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
rootlist = [[] for i in range(n)]
flag = [False]*n

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

que = deque([1])
while que:
    now = que.popleft()
    for room in rootlist[now-1]:
        if flag[room-1] == False:
            flag[room-1] = now
            que.append(room)

print('Yes')
for root in flag[1:]:
    print(root)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
rootlist = [[] for i in range(n)]
flag = [False for i in range(n)]

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

que = deque()
que.append(1)
while len(que) !=0:
    now = que.popleft()
    for room in rootlist[now-1]:
        if flag[room-1] == False:
            flag[room-1] = now
            que.append(room)

print('Yes')
for root in flag[1:]:
    print(root)