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())
g = [[] for _ in range(n)]
for _ 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
ans = [0]*n
print("Yes")

while q:
    p = q.popleft() # 先に入れた要素を取り出す
    for node in g[p]:
        if d[node] == -1:
            d[node] = d[p] + 1
            q.append(node) # リストへの追加
        else:
            if d[node] + 1 == d[p]:
                ans[p] = node + 1

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from collections import deque

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

way=[[] for i in range(N)]

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

visited=[-1 for i in range(N)]
visited[0]=0
dq=deque([0]) #loc,value

while dq:
    temp=dq.popleft()
    for item in way[temp]:
        if visited[item]==-1:
            visited[item]=temp
            dq.append(item)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

icase=0
if icase==0:
    n,m=map(int,input().split())
    g = [[] for _ in range(n)]
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
elif icase==1:
    n,m=4,4
    g=[[1], [0, 2, 3], [1, 3], [2, 1]]
elif icase==2:
    n,m=6,9
    g=[[5, 4], [3, 5], [3, 4], [2, 1, 5, 4], [2, 0, 3, 5], [0, 3, 1, 4]]

q=deque([0])

stack=[0]
parent=[-1]*n
parent[0]=0
dist=[-1]*n
dist[0]=0
while q:
    state = q.popleft()
#    print("--- q:",q,"state:",state,"g:",g[state],"p:",parent)
    for v in g[state]:
#        print("  state:",state,"v:",v,"q:",q)
#        if parent[state] == v:
        if parent[v] !=-1:
            continue
        else:
#            print("parent:",parent,"xx:",xx,"stack",stack)
            parent[v]=state
            dist[v]=dist[state]+1
            q.append(v)
#            print(" state:",state,"v:",v,"parent:",parent,"stack",stack,"dist[v]",dist[v])
for i in range(1,n):
    if parent[i]==-1:
        print("No")
        sys.exit()

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

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    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)        
    # print(to)
    guide = [0] * N
    guide[0] = 1
    q = deque()
    q.append(0)
    while len(q) > 0:
        u = q.popleft()
        for v in to[u]:
            # print(guide)
            if guide[v] != 0:
                continue
            guide[v] = u+1
            q.append(v)

    print("Yes")
    for g in guide[1:]:
        print(g)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue

N, M = map(int,input().split(' '))
#AB=[]
Root=[]
Sign=[]

for i in range(N+1):
    Root.append([])
    Sign.append(0)
#print(Root)

for i in range(M):
    a,b = map(int,input().split(' '))
    #AB.append([a,b])
    Root[a].append(b)
    Root[b].append(a)

q = queue.Queue()
q.put(1)

while not q.empty():
    r = q.get()
    for nextR in Root[r]:
        if Sign[nextR] == 0:
            q.put(nextR)
            Sign[nextR]=r

if 0 in Sign[1:]:
    print('No')
else:
    print('Yes')
    for i in range(2,N+1):
        print(Sign[i])

Submission status: Accepted

Solution code:
from collections import deque

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

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

for a,b in ab:
  c[a].append(b)
  c[b].append(a)
seen = [float('inf')]*(n+1)
que=deque()
que.append(1)
seen[1] = 0
while que:
  s=que.popleft()
  for i in c[s]:
    if seen[i] == float('inf'):
      que.append(i)
      seen[i] = s
if sum(seen[2:]) == float('inf'):
  print('No')
else:
  print('Yes')
  for i in seen[2:]:
    print(i)

Submission status: Accepted

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

from collections import deque
def solve():
    prev = [-1]*N
    prev[0]='Yes'
    d = deque([(0,0)])
    while len(d):
        v,cnt = d.popleft()
        for u in edge[v]:
            if prev[u]==-1:
                prev[u]=v+1
                d.append((u,cnt+1))
    if -1 in prev:
        return ['No']
    return prev
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
def bfs():
    visited=[-1]*n
    q=deque()
    start=1
    visited[start-1]=0
    q.append(start)
    while q:
        now=q.popleft()
        for next in graph[now-1]:
            if visited[next-1]==-1:
                q.append(next)
                visited[next-1]=now
    return visited[1:]

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

graph = [[] for _ in range(n)]
for v in p:
    graph[v[0]-1].append(v[1])
    graph[v[1]-1].append(v[0])  # 有向グラフなら消す

#print(graph)  # [[2, 3, 5], ..., [1, 3, 4]]

ans=bfs()
if -1 in ans:
    print('No')
else:
    print('Yes')
    for i in ans:
        print(i)

Submission status: Accepted

Solution code:
from collections import deque

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

d = deque()
d.append(1)
ans = [-1] * (n+1)
ans[1] = 1
while d:
    f = d.popleft()
    for t in ex[f]:
        if ans[t] == -1:
            ans[t] = f
            d.append(t)

for i in range(2, n+1):
    if ans[i] == -1:
        print('No')
        exit()

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

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    ans = [0]*n
    dist = [-1]*n
    que = deque([0])
    dist[0] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in g[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            ans[w] = v + 1
            que.append(w)
    return ans[1:]

n, m = MAP()
g = [[] for i in range(n)]
for i in range(m):
    A, B =MAP()
    g[A-1].append(B-1)
    g[B-1].append(A-1)

print("Yes")
for x in bfs():
    print(x)

Submission status: Accepted

Solution code:
from collections import deque

N,M=map(int,input().split())
graph=[[] for i 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]*(N+1)
dist[0]=0
dist[1]=0
d=deque()
d.append(1)
ans=[0]*(N+1)
while d:
    v=d.popleft()
    for i in graph[v]:
        if dist[i]!=-1:
            continue
        dist[i]=dist[v]+1
        d.append(i)
        if ans[i]!=0:
            continue
        ans[i]+=v
print("Yes")
for i in ans:
    if i==0:
        continue
    print(i)

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N, LIST):
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    PATH = [-1 for _ in range(N)]
    PATH[S] = 's'
    frag, que = set([S]), deque([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:
            if i in frag:
                continue
            PATH[i] = q
            que.append(i), frag.add(i)
    return PATH


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

near = nearlist(n, ab)
path = bfs(near, 0, n)

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

Submission status: Accepted

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

A = []
B = []

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

P = [[] for _ in range(N + 1)]

for a, b in zip(A, B):
    P[b].append(a)
    P[a].append(b)

ans = [0] * (N + 1)
ans[1] = 1
next_numbers = [1]

while next_numbers:
    check_number = next_numbers[:]
    next_numbers = []
    for number in check_number:
        for x in P[number]:
            if ans[x] == 0:
                ans[x] = number
                next_numbers.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())
AB = [list(map(int, input().split())) for _ in range(M)]
prev = [0] * N
to_list = [ [] for _ in range(N)]
for a,b in AB:
 to_list[a - 1].append(b - 1)
 to_list[b - 1].append(a - 1)
marked = {0}
que = [0]
for i in que:
   for j in to_list[i]:
       if j in marked: continue
       que.append(j)
       marked.add(j)
       prev[j] = i+1
print('Yes')
print(*prev[1:], sep='\n')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())   #n=部屋 m=通路
adj = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

from collections import deque
q = deque()

dis = [-1] * n
ans = [0] * n

q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dis[to] != -1:
            continue
        dis[to] = dis[now] + 1
        q.append(to)
        ans[to] = now
print("Yes")
for i in range(1,n):
    print(ans[i] + 1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

q = deque([1])
s = [1] + [0] * n

while q:
    u = q.popleft()
    for v in l[u]:
        if not s[v]:
            s[v] = u
            q.append(v)
print('Yes')

for i in range(2, n + 1):
    print(s[i])

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
road=[[] for i in range(n)]
#隣接行列表現だとo(n^2)で間に合わないので隣接リスト表現でいく
for i in range(m):
  a,b=list(map(int,input().split()))
  road[a-1].append(b)
  road[b-1].append(a)
from collections import deque
q=deque([1])
check=[0 for i in range(n)]
check[0]=1
ans=[0 for i in range(n)]
while len(q)>0:
  p=q.popleft()
  for i in range(len(road[p-1])):
    if check[road[p-1][i]-1]==0:
      q.append(road[p-1][i])
      check[road[p-1][i]-1]=1
      ans[road[p-1][i]-1]=p
      
      
print("Yes")
for i in range(1,n):
  print(ans[i])

Submission status: Accepted

Solution code:
import collections

N, M = map(int, input().split())
AB = []
for m in range(M):
    a, b = map(int, input().split())
    AB.append((a, b))

Cost = [[] for l in range(N+1)]
R = [0]*(N+1)
#print(Cost)

for a, b in AB:
    Cost[a].append(b)
    Cost[b].append(a)

#print(AB)
#print(Cost)

Rcount = 0
Pipod = collections.deque()
Pipod.append(1)
while Rcount != N-1:
    #print(Pipod)
    p = Pipod.popleft()
    #print(Cost[p])
    for c in Cost[p]:
        if c != 1 and R[c] == 0:
            R[c] = p
            Pipod.append(c)
            Rcount += 1
    if len(Pipod) == 0:
        print('No')
        exit(0)

print('Yes')
for x in R[2:N+1]:
    print(x)

Submission status: Accepted

Solution code:
from collections import deque
N, M = list(map(int, input().split()))

g = [[] for _ in range(N)]
sign = [-1 for _ in range(N)]

for _ in range(M):
    a, b = list(map(int, input().split()))

    g[a-1].append(b-1)
    g[b-1].append(a-1)

queue = deque()
queue.append(0)

while len(queue) > 0:

    now = queue.popleft()

    for adj in g[now]:
        if sign[adj] == -1:
            queue.append(adj)
            sign[adj] = now


allVisited = True

for i in range(1, len(sign)):
    if sign[i] == -1:
        allVisited = False

if not allVisited:
    print("No")
    exit()

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

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
E={i:[] for i in range(1,N+1)}
for i in range(M):
    a,b=list(map(int,input().split()))
    E[a].append(b)
    E[b].append(a)
V={i:0 for i in range(1,N+1)}
W=[1]
while W!=[]:
    S=[]
    for a in W:
        for b in E[a]:
            if V[b]==0:
                V[b]=a
                S.append(b)
    W=S
if -1 in V:
    print('No')
else:
    print('Yes')
    for i in range(2,N+1):
        print(V[i])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import deque
from copy import deepcopy
def main():
    n, m = map(int, input().split())
    edges = {e:[] for e in range(n + 1)}
    for _ in range(m):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)

    res = [0] * (n + 1)
    dist = 1
    distroom = [n + 1] * (n + 1)
    distroom[1] = 0
    q1 = deque()
    q2 = deque()
    q1.append(1)
    while q1:
        for q1e in q1:
            for adj in edges[q1e]:
                if distroom[adj] > dist:
                    res[adj] = q1e
                    distroom[adj] = dist
                    q2.append(adj)
        dist += 1
        q1 = deepcopy(q2)
        q2 = deque()
    print('Yes')
    print(*res[2:],sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

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

coriddorList = [set() for i in range(n+1)]
deepList = [-1 for i in range(n+1)]


for i in range(m):
    a,b = list(map(int,input().split()))
    coriddorList[a].add(b)
    coriddorList[b].add(a)

checkList = [0] * (n + 1)
ansList = [0] * (n + 1)
checkList[1] = 1
q = collections.deque()
q.appendleft(1)

while len(q) > 0:
    value = q.pop()
    for k in coriddorList[value]:
        if checkList[k] == 0:
            checkList[k] = 1
            ansList[k] = value
            q.appendleft(k)

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

Submission status: Accepted

Solution code:
from collections import deque

INF = 9999999

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)

que = deque([0])
dist = [INF] * N
pre = [0] * N
dist[0] = 0
while que:
    from_v = que.popleft()
    for to_u in to[from_v]:
        if dist[to_u] != INF:
            continue
        dist[to_u] = dist[from_v]+1
        pre[to_u] = from_v
        que.append(to_u)

print('Yes')
for i in range(N):
    if i == 0:
        continue
    print(pre[i]+1)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n)]

for _ 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
ans = [0]*n
print('Yes')
while q:
    p = q.popleft()
    for node in g[p]:
        if d[node] == -1:
            d[node] = d[p] + 1
            q.append(node)
        else:
            if d[node] + 1 == d[p]:
                ans[p] = node + 1
for i in range(1, n):
    print(ans[i])

Submission status: Accepted

Solution code:
print('Yes')

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)

ans = [-1] * (n+1)
ans[0] = 0
ans[1] = 0

d = deque()
d.append(1)

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

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

Submission status: Accepted

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

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

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

from collections import deque
q = deque()

dist = [-1] * n
ans = [0] * n

q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] != -1:continue
        dist[to] = dist[now] + 1
        q.append(to)
        ans[to] = now

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

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
road = [[] for _ in range(N+1)]
ans = [-1]*(N+1)
d = deque()
for i in range(M):
    A, B = map(int, input().split())
    road[A].append(B)
    road[B].append(A)
d.append(1)
while len(d) != 0:
    look = d.popleft()
    for i in road[look]:
        if ans[i] == -1:
            d.append(i)
            ans[i] = look

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

Submission status: Accepted

Solution code:
import sys
from collections import *

N,M=map(int,input().split())
adj=[[] for _ in range(N+1)]
for ln in sys.stdin:
    A,B=map(int,ln.split())
    adj[A].append(B)
    adj[B].append(A)

ans=[0]*(N+1)
ans[1]=1
que=deque([1])
while que:
    A=que.popleft()
    for B in adj[A]:
        if ans[B]==0:
            ans[B]=A
            que.append(B)

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

Submission status: Accepted

Solution code:
import sys
from collections import *

N,M=map(int,input().split())
adj=defaultdict(list)
for ln in sys.stdin:
    A,B=map(int,ln.split())
    A,B=A-1,B-1
    adj[A].append(B)
    adj[B].append(A)

a={0:0}
que=deque([0])
while que:
    u=que.popleft()
    for v in adj[u]:
        if v not in a:
            a[v]=u
            que.append(v)

if N-1-len(a)>0:
    print('No')
else:
    print('Yes')
    for i in range(1,N):
        print(a[i]+1)

Submission status: Accepted

Solution code:
import sys
N,M=map(int,input().split())
adj={}
for ln in sys.stdin:
    A,B=map(int,ln.split())
    if A not in adj: adj[A]=[]
    if B not in adj: adj[B]=[]
    adj[A].append(B)
    adj[B].append(A)

a=[0]*(N+1)
a[1]=-1
que=[1]
while que:
    suc=[]
    for u in que:
        for v in adj[u]:
            if a[v]!=0:
                continue
            a[v]=u
            suc.append(v)
    que=suc

#print(N,M)
#print(adj)
#print(a)

ok=True
ans=[]
for i in range(2,N+1):
    if a[i]==0:
        ok=False
        break
    ans.append(a[i])

if not ok:
    print('No')
else:
    print('Yes')
    for x in ans:
        print(x)

Submission status: Accepted

Solution code:
#問題文に連結と書いてあるのでどの部屋も互いに行き来できる
#自分がきたところを記録する幅優先探索をすればいい
n,m=list(map(int,input().split()))
#道を隣接リスト表現で表す
road=[[] for i in range(n)]
for i in range(m):
  a,b=list(map(int,input().split()))
  road[a-1].append(b)
  road[b-1].append(a)
#幅優先探索
from collections import deque
q=deque([1])
ans=[0 for i in range(n)]
check=[0 for i in range(n)]
check[0]=1
while len(q)>0: 
  p=q.popleft()
  for j in road[p-1]:
    if check[j-1]==0:
      q.append(j)
      check[j-1]=1
      ans[j-1]=p

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

Submission status: Accepted

Solution code:

from collections import deque

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

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

INF = 10 ** 9 + 7
d = [INF] * (N + 1)
ans = [0] * (N + 1)
q = deque([1])
d[1] = 0
while q:
    u = q.popleft()
    for v in graph[u]:
        if d[v] > d[u] + 1:
            d[v] = d[u] + 1
            ans[v] = u
            q.append(v)

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

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 n in graph[current]:
            if dist[n] != -1:
                continue
            else:
                dist[n] = dist[current] + 1
                prev[n] = current
                queue.append(n)

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 n in prev[2:]:
        print(n)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal #floatの高精度ver, 渡すのはstr型で
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n,m=map(int,input().split())

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

flag=[-1]*n
flag[0]=0

queue=deque([ [0,i] for i in A[0] ])
now=0
while queue:
    now,to=queue.pop()
    # print("now to",now,to)
    if flag[to]==-1:
        flag[to]=now
        for i in A[to]:
            queue.appendleft([to,i])

# print(flag)
if -1 in flag:
    print("No");exit()
print("Yes")
for i in range(1,n):
    print(flag[i]+1)

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,m = readInts()
G = [[] for _ in range(n)]
for i in range(m):
    a,b = map(lambda x:int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
q = deque([0])
def pa():
    while q:
        v = q.popleft()
        for nv in G[v]:
            if arrived[nv] < 0:
                arrived[nv] = v + 1
                q.append(nv)
arrived = [-1] * n
pa()
if -1 in arrived[1:]:
    print('No')
else:
    print('Yes')
    print(*arrived[1:],sep='\n')

Submission status: Accepted

Solution code:
import networkx as nx
N, M = map(int, input().split())

G = nx.Graph()

G.add_edges_from(tuple(map(int, input().split())) for _ in range(M))

dist = nx.shortest_path_length(G, target=1)
print('Yes')
for i in range(2, N+1):
  print(min((dist[j], j) for j in nx.all_neighbors(G, i))[1])

Submission status: Accepted

Solution code:
from collections import deque

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

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

queue = deque([1])
visited = [-1] * n
parent = [0] * n
now = 1

visited[0]=0

while len(queue) > 0:
    now = queue.popleft()
    for i in aisle[now-1]:
        if visited[i-1]==-1:
            queue.append(i)
            visited[i-1]=visited[now-1]+1
            parent[i-1] = now


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

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N, M = [int(i) for i in input().strip().split()]
    graph = [[] for _ in range(N)]
    sign = [0] * N
    for _ in range(M):
        a, b = [int(i) for i in input().strip().split()]
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    candidates = deque([0])
    visited = [False] * N
    visited[0] = True
    while len(candidates) > 0:
        v = candidates.popleft()
        for i in graph[v]:
            if visited[i]:
                continue
            visited[i] = True
            sign[i] = v
            candidates.append(i)
    print("Yes")
    for i in sign[1:]:
        print(i + 1)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

from collections import deque

queue = deque([0])
visit = [-1] * N
visit[0] = 1

while queue:
    now = queue.popleft()
    for u in adj[now]:
        if visit[u] < 0:
            queue.append(u)
            visit[u] = visit[now] + 1

print('Yes')
for i in range(1,N):
    for u in adj[i]:
        if visit[u] == visit[i]-1:
            print(u+1)
            break

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().split())
g = [[] for _ in range(n)]

for _ in range(m):
  a,b = map(int, input().split())
  a,b = a-1, b-1
  g[a].append(b)
  g[b].append(a)
stack = deque([0])
dist = [-1]*n
dist[0] = 0

while stack:
  v = stack.popleft()
  for nv in g[v]:
    if dist[nv] == -1:
      dist[nv] = v+1
      stack.append(nv)

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

Submission status: Accepted

Solution code:
import heapq
INFTY = 10**6
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
dist = [INFTY for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
heap = [(0,1)]
dist[1] = 0
hist[1] = 1
pre = {1:0}
while heap:
    d,x = heapq.heappop(heap)
    if d>dist[x]:continue
    for y in G[x]:
        if hist[y]==0:
            if dist[y]>d+1:
                dist[y] = d+1
                pre[y] = x
                heapq.heappush(heap,(d+1,y))
flag = 0
for i in range(1,N+1):
    if dist[i]>=INFTY:
        flag = 1
        break
if flag==1:
    print("No")
else:
    print("Yes")
    for i in range(2,N+1):
        print(pre[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

prev = [-1] * N
visited = [0] * N
visited[0] = 1
from collections import deque
q = deque([0])
while q:
    v = q.popleft()
    for to in es[v]:
        if visited[to]: continue
        visited[to] = 1
        prev[to] = v
        q.append(to)

print('Yes')
for p in prev[1:]:
    print(p+1)

Submission status: Accepted

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

def bfs():
    q = deque([0])
    pre = [-1]*N
    pre[0] = 0
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if pre[nv]==-1:
                pre[nv] = v
                q.append(nv)
    
    return pre

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

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

pre = bfs()
print('Yes')

for pre_i in pre[1:]:
    print(pre_i+1)

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)

from collections import deque
q = deque([])
q.append(0)
visit = [-1]*n
visit[0] = 0
while q:
    v = q.popleft()
    for u in g[v]:
        if visit[u] == -1:
            visit[u] = v
            q.append(u)
print('Yes')
for i in range(1, n):
    print(visit[i]+1)

Submission status: Accepted

Solution code:
import queue

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

ans = [-1 for _ in range(n)]
ans[0] = 0
q = queue.Queue()
q.put(0)
while not q.empty():
    start = q.get()
    for end in maze[start]:
        if ans[end] == -1:
            q.put(end)
            ans[end] = start

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[[]for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    s[a-1].append(b-1)
    s[b-1].append(a-1)
t=[-1]*n
q=[0]
while q:
    p=[]
    for j in q:
        for i in s[j]:
            if i!=j and t[i]==-1:
                p.append(i)
                t[i]=j
    q=p[::]
print("Yes")
for i in t[1:]:
    print(i+1)