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:
#D
from collections import deque
n,m = map(int,input().split())
#インデックス→各部屋番号(-1),つながってる部屋の番号を格納
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までの距離(初期値999)
bango = [-999 for _ in range(n)]
bango[0] = 0

#p->今いる部屋
p = deque()
p.append(0)

while not len(p)==0:
    x = p.pop()
    for i in graph[x]:
        if bango[i] != -999:
            pass
        else:
            p.appendleft(i)
            #i番目の部屋はxからいける
            bango[i] = x
print('Yes')
for i in range(1,n):
    print(bango[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

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

INF=100050

q=deque()

class Room:
    def __init__(self,num):
        self.number=num
        self.frontier=True
        self.neighbor=[]
        self.arrow=0
        self.deepness=INF

    def set(self,room):
        self.neighbor.append(room)
    
    def search(self,num,deps):
        self.arrow=num
        self.deepness=deps
        self.frontier=False

    def dfs(self):
        for i in self.neighbor:
            if rooms[i].frontier:
                rooms[i].search(self.number,self.deepness+1)
                q.append(i)

rooms=[]
for i in range(n+1):
    rooms.append(Room(i))

for _ in range(m):
    a,b=map(int,input().split())
    rooms[a].set(b)
    rooms[b].set(a)

q.append(1)
while q:
    rooms[q.popleft()].dfs()


print("Yes")
for i in range(2,len(rooms)):
    if rooms[i].frontier==False:
        print(rooms[i].arrow)

Submission status: Accepted

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

from collections import deque
q = deque()
reach = [None] + [0] + [-1]*(n-1)
goal  = [None] + [0]*n
for L in V[1]:
    q.append(L)
    reach[L] = reach[1] + 1
    goal[L] = 1
while q:
    p = q.popleft()
    for L in V[p]:
        if reach[L] == -1:
            q.append(L)
            reach[L] = reach[p] + 1
            goal[L] = p
print("Yes")
for i in range(len(goal)-2):
    print(goal[i+2])

Submission status: Accepted

Solution code:
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)
ANS=[0 for i in range(N)]
finish=[0]
for i in finish:
  for k in graph[i]:
    if ANS[k]==0:
      ANS[k]=i+1
      finish.append(k)
print("Yes")
for i in range(1,N):
  ans=ANS[i]
  print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy
from collections import deque
from collections import defaultdict

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

line=defaultdict(list)
q=deque
next=deque()

ans=[-1]*(N+1)
ans[0]=0
ans[1]=0
for i in range(M):
  a,b=map(int, input().split())
  line[a].append(b)
  line[b].append(a)

#print(line)
    
next.append(1)
a=1
while len(next)>0:
  q=copy.copy(next)
  #print(q)
  next.clear()
  while len(q)>0:
    chk=q.popleft()
    #print('qpop',q)
    for i in range(len(line[chk])):
      #print('chk',chk)
      #print('line[chk][i]',line[chk][i])
      if ans[line[chk][i]]==-1:
        ans[line[chk][i]]=chk
        next.append(line[chk][i]) 
  if -1 not in ans:break
  #print('next',next)
#print(ans)
if -1 in ans:print('No')
else:
  print('Yes')
  for i in range(2,N+1):  
    print(ans[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

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

# calc
inf = 1001001001
dist = [inf for _ in range(n)]
pre = [-1 for _ in range(n)]
dist[0] = 0 
q = deque()
q.append(0)

while q:
    v = q.popleft()
    for u in to[v]:
        if dist[u] == inf:
            dist[u] = dist[v] + 1 
            pre[u] = v 
            q.append(u)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

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

# calc
inf = 1001001001
dist = [inf for _  in range(n)]
pre = [-1 for _ in range(n)]
dist[0] = 0 
q = deque()
q.append(0)

while q:
    v = q.popleft()
    for u in to[v]:
        if dist[u] != inf:
            continue
        dist[u] = dist[v]+1
        pre[u] = v 
        q.append(u)

# output
print('Yes')
for i in range(n):
    if i == 0:
        continue
    ans = pre[i]
    ans +=1 
    print(ans)

Submission status: Accepted

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

graph = [[] for _ in range(n)]
for i in range(m):
    graph[a[i] - 1].append(b[i] - 1)
    graph[b[i] - 1].append(a[i] - 1)

pathway = [None for _ in range(n)]
queue = [0]
depth = [-1]*n
depth[0] = 0
pre = [-1]*n

while queue:
    now = queue.pop(0)
    for i in graph[now]:
        if depth[i] == -1:
            if pre[i] == -1:
                pre[i] = now
            depth[i] = depth[now] + 1
            queue.append(i)

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

Submission status: Accepted

Solution code:
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)

from collections import deque

def bfs(u):
    queue = deque([u])
    d=[-1]*n
    pre=[-1]*n
    d[u]=0
    while queue:
        v=queue.popleft()
        for i in g[v]:
            if d[i] is -1:
                if pre[i] == -1:
                    pre[i]=v
                d[i]=d[v]+1
                queue.append(i)
    return d,pre
d,pre=bfs(0)
print('Yes')

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

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        adj[A-1].add(B-1)
        adj[B-1].add(A-1)
    ans = [-1] * N
    q = deque([(0, 0)])
    while len(q):
        cur, prev = q.popleft()
        if ans[cur] != -1:
            continue
        ans[cur] = prev
        for nxt in adj[cur]:
            if ans[nxt] == -1:
                q.append((nxt, cur))
    print("Yes")
    for i in range(1, N):
        print(ans[i]+1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
inf = 10**9
sys.setrecursionlimit(inf)


def connect(signs, to_room, from_room):
    signs[to_room][2].add(from_room)
    signs[from_room][2].add(to_room)
    return signs


def update(signs, to_room, from_room):
    """
    1. fromの距離を記憶
    2. fromの行き先を記憶
    3. toの来るリストにfromを追加
    4. fromの行き先にtoを追加
    5. fromの距離をto+1に変更
    6. もともとのfromの距離がinfなら
        a. fromの来るリスト(fromfrom)の行き先をfromにする
        b. fromfromの来るリストからfromを削除
        c. 1から始める
    7. fromの新しい距離がもともとのfromの行き先(fromto)の距離がより短いなら、
        a. 1から始める
    """
    # from_room_dist = signs[from_room][0]
    # from_to_rooms = signs[from_room][1]
    # signs[to_room][2].add(from_room)
    # signs[to_room][2].discard(from_room)
    signs[from_room][0] = signs[to_room][0] + 1
    signs[from_room][1] = to_room
    # signs[from_room][2].discard(to_room)
    for from_from_room in signs[from_room][2]:
        if signs[from_room][0] < signs[from_from_room][0] - 1:
            signs = update(signs, from_room, from_from_room)
    # if from_room_dist == inf:
    #     for from_from_room in signs[from_room][1]:
    #         signs[from_from_room][1].discard(from_room)
    #         signs = update(signs, from_room, from_from_room)
    for from_to_room in signs[from_room][2]:
        if from_to_room and signs[from_room][0] < signs[from_to_room][0] - 1:
            signs = update(signs, from_room, from_to_room)
        # print(signs)
    return signs


def main():
    n, m, *ab = map(int, open(0).read().split())
    ab = [ab[2 * i:2 * (i + 1)] for i in range(m)]

    to = [[] for _ in range(n)]
    for a, b in ab:
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)

    dist = [inf] * n
    pre = [None] * n
    queue = [0]
    while queue:
        v = queue.pop(0)
        for u in to[v]:
            if dist[u] != inf:
                continue
            dist[u] = dist[v] + 1
            pre[u] = v
            queue.append(u)

    pre = [i + 1 for i in pre]
    ans = '\n'.join([str(i) for i in ['Yes'] + pre[1:]])

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)

from collections import deque
q = deque([0])

INF = float('inf')
dist = [INF] * N
dist[0] = 0
back = [-1] * N

while q:
  v = q.popleft()
  for to in es[v]:
    #ここのロジックの意味がまだわかっていない
    if dist[v] + 1 >= dist[to]: continue
    dist[to] = dist[v]
    back[to] = v+1
    q.append(to)

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

Submission status: Accepted

Solution code:
import collections
from collections import deque

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

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

michi = [None for i in range(n)]
q = deque([0])
while q:
    pop = q.popleft()
    for i in li[pop]:
        if michi[i] is None:
            michi[i] = pop
            q.append(i)
print("Yes")
for i in range(1,len(michi)):
    print(michi[i]+1)

Submission status: Accepted

Solution code:
import sys
import math
import collections
from collections import deque
from functools import reduce
import heapq
#t = int(input())
n, m = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))

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

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    l[a-1].append(b-1)
    l[b-1].append(a-1)

ans = [None for i in range(n)]
q = deque([0])
while q:
    u = q.popleft()
    for i in l[u]:
        if ans[i] is None:
            ans[i] = u
            q.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque
def bfn():
    q=deque([0])
    visit[0]=True
    while q:
        room_proper=q.popleft()
        for i in graph[room_proper]:
            if visit[i]==False:
                visit[i]=True
                shirube[i]=room_proper
                q.append(i)



if __name__ == "__main__":

    n,m=map(int,input().split())
    shirube=[0]*n
    b=[]
    visit=[False]*n
    graph=[[]*n for _ in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        a-=1
        b-=1
        graph[a].append(b)
        graph[b].append(a)
    bfn()

    if all(visit)==True:
        print("Yes")
        for i in range(1,n):
            print(shirube[i]+1)
    else:
        print("No")

Submission status: Accepted

Solution code:
from collections import deque

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

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

def bfs(maze,start):
    queue=deque([start])
    d=[float("inf")]*N
    d[start]=0
    while queue:
        x=queue.popleft()
        for y in graph[x]:
            if d[y]==float("inf"):
                d[y]=d[x]+1
                queue.append(y)
    return d

d=bfs(graph,0)
ans=[0]*N
for i in range(1,N):
    flag=0
    for vertex in graph[i]:
        if d[vertex]==d[i]-1:
            ans[i]=vertex+1
            flag=1
            break
    if flag==0:
        print("No")
        exit()
print("Yes")
print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque

# 初期化周り
N, M = map(int, input().rstrip().split())
G = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().rstrip().split())
    G[A].append(B)
    G[B].append(A)

# 目印
sign = [-1]*(N+1)
sign[0] = None
sign[1] = 0

queue = deque([1])

while queue:
    node = queue.popleft()
    for next in G[node]:
        if sign[next] > -1:
            continue
        sign[next] = node
        queue.append(next)

if -1 in sign:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(sign[i])

Submission status: Accepted

Solution code:
import networkx as nx
room, route_count = map(int,input().split())
route = [list(map(int,input().split())) for _ in range(route_count)]

G = nx.Graph()
G.add_nodes_from(range(1,room+1))
G.add_edges_from(route)
pre = nx.predecessor(G, 1)

print('Yes')
for i in range(2,room+1):
  print(pre[i][0])

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
to=[[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)
dist=[None]*n    

que=deque([0])
while que:
    v=que.pop()
    for i in to[v]:
        if(dist[i] is None):
            dist[i]=v+1
            que.appendleft(i)
        
print("Yes")
for i in dist[1:]:
    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)
    queue = deque([1])
    while queue:
        parent = queue.pop()
        children = to[parent]
        for child in children:
            if ans[child] is None:
                ans[child] = parent
                queue.appendleft(child)
    print("Yes")
    print("\n".join(list(map(str, ans[2:]))))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


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

    n, m = map(int, input().split())
    p = [[] for _ in range(n)]
    d = deque()
    d.append(0)
    is_used = [False for _ in range(n)]
    is_used[0] = True
    ans = [0 for _ in range(n)]

    for i in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1

        p[ai].append(bi)
        p[bi].append(ai)

    while d:
        di = d.popleft()

        for e in p[di]:
            if is_used[e]:
                continue

            is_used[e] = True
            ans[e] = di + 1

            d.append(e)

    print('Yes')
    print('\n'.join(map(str, ans[1:])))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import deque 
def main():
    n, m = map(int, readline().split())
    to = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, readline().split()) 
        a-=1
        b-=1
        to[a].append(b)
        to[b].append(a)

    dq = deque()    
    dq.append(0)
    done = [-1 for _ in range(n)]
    done[0] = 1 
    while len(dq)>0:
        v = dq.popleft()
        for nx in to[v]:
            if done[nx] != -1:
                continue
            done[nx] = v
            dq.append(nx)

    print('Yes')
    for i in done[1:]:
        print(i+1)
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)
    
def bfs(graph, N):
    que = deque([0])
    dist = [-1]*N
    dist[0]=0
    while que:
        i = que.popleft()
        for j in graph[i]:
            if dist[j] < 0:
                que.append(j)
                dist[j]=i+1
    return dist

dist = bfs(graph, n)[1:]

if all([x>=0 for x in dist]):
    print("Yes")
    for i in dist:
        print(i)
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
import queue
n,m = map(int, sys.stdin.readline().rstrip("\n").split())
adj = [[]for i in range(n+1)]
parent = [-1] * (n+1)
for line in sys.stdin:
    a,b = map(int, line.rstrip("\n").split())
    adj[a].append(b)
    adj[b].append(a)
q = queue.Queue()
q.put((1,0))
while(not q.empty()):
    x, p = q.get()
    if parent[x] != -1: # 訪問済み
        continue
    parent[x] = p
    for next in adj[x]:
        if parent[next] == -1: # 未訪問なら
            q.put((next,x))
print ('Yes') # 必ず目標は達成できる
for p in parent[2:]: # 部屋2以降の親（前の部屋）
    print(p)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
q = deque()
t = {i: set() for i in range(1, n + 1)}
v = [-1] * n

for _ in range(m):
    a, b = map(int, input().split())
    t[a].add(b)
    t[b].add(a)
q.append(1)
v[0] = 1
while q:
    next = q.popleft()
    for i in t[next]:
        if v[i - 1] == -1:
            q.append(i)
            v[i - 1] = next
print('Yes')
print(*v[1:], sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
numbers=[[] for _ in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    numbers[A-1].append(B-1)
    numbers[B-1].append(A-1)
visited=[-1 for _ in range(N)]
visited[0]=1
stack=deque([0])
inf=pow(10,9)
distances=[inf for _ in range(N)]
distances[0]=0
visited=[0 for _ in range(N)]
while len(stack) > 0:
    x=stack.pop()
    for a in numbers[x]:
        if distances[a]>distances[x]+1:
            visited[a]=x+1
            distances[a]=distances[x]+1
            stack.appendleft(a)
distances[0]=0
print('Yes')
for a in range(1,N):
    print(visited[a])

Submission status: Accepted

Solution code:
#関数を持ってくる
from collections import deque

#入力
n,m = map(int,input().split())
ab_list = [list(map(int,input().split())) 
           for nesya in range(m)]

#roomのリストを作る
room = [0]*n

#ある部屋に繋がっている部屋のリストを作り、入れる
route = [[] for motsu in range(n)]
for ab in ab_list:
  a = ab[0]
  b = ab[1]
  route[a-1].append(b)
  route[b-1].append(a)

d = deque()
d.append(1)
while len(d) > 0:
  s = d.popleft()
  s_list = route[s-1]
  for h in s_list:
    if room[h-1] != 0:
      continue
    room[h-1] = s
    d.append(h)
ans = room[1:]
if 0 in ans:
  print('No')
else:
  print('Yes')
  for w in ans:
    print(w)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
graph = [list() for _ in range(N)]

for _ in range(M):
    u, k=[int(x) for x in input().split()] # uは頂点番号、kは隣接頂点の個数
    graph[u-1].append(k-1)
    graph[k-1].append(u-1) # 無向グラフ
#print(graph)

sign = [0]*(N-1)#どこを通るか
dist=[N]*N#距離
dist[0]=0#startは0

q=deque()
q.append(0)
while q:#qが空になるまで
    v=q.popleft()
    for x in graph[v]:
        if dist[x] > dist[v]+1:#更新
            dist[x]=dist[v]+1
            sign[x-1]=v+1
            q.append(x)
#print(dist)
print("Yes")
for i in sign:
    print(i)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def bfs(graph, N, start):
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = node + 1
                que.append(n)
    return visited

def main():
    #n = int(stdin.readline().rstrip())
    n,m = map(int, stdin.readline().rstrip().split())
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b = map(int, stdin.readline().rstrip().split())
        a-=1;b-=1 #indexに直す
        graph[a].append(b)
        graph[b].append(a)
    visited = bfs(graph, n, 0)
    print("Yes")
    for i in range(1,n):
        print(visited[i])

main()

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
g = [[] for _ in range(N + 1)]  # 部屋mにつながっている部屋一覧
for m in range(M):
    a, b = list(map(int, input().split()))
    if a <= N and b <= N:
        g[a].append(b)
        g[b].append(a)

queue = [1]
d = [None] * (N + 1)
d[0] = 0
d[1] = 0
while queue:
    v = queue.pop(0)
    for i in g[v]:
        # print('g[v]',g[v])
        if d[i] is None:
            d[i] = v
            queue.append(i)
        # print('d[i]',d[i],'queue',queue)
for i in range(N + 1):
    if d[i] is None:
        print('No')
        exit()
print('Yes')
for i in range(2, N + 1):
    print(d[i])

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
g = [[] for _ in range(N + 1)]  # 部屋mにつながっている部屋一覧
for m in range(M):
    a, b = list(map(int, input().split()))
    if a <= N and b <= N:
        g[a].append(b)
        g[b].append(a)

queue = [1]
d = [None] * (N + 1)
d[0] = 0
# d[1] = 0
while queue:
    v = queue.pop(0)
    for i in g[v]:
        # print('g[v]',g[v])
        if d[i] is None:
            d[i] = v
            queue.append(i)
        # print('d[i]',d[i],'queue',queue)
for i in range(N + 1):
    if d[i] is None:
        print('No')
        exit()
print('Yes')
for i in range(2, N + 1):
    print(d[i])

Submission status: Accepted

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

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

ans = [-1] * N
q = [0]
while len(q) > 0:
    nq = []
    for t in q:
        for e in bridges[t]:
            if ans[e] < 0:
                nq.append(e)
                ans[e] = t
    q = nq

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = list(map(int, input().split()))
connects = [[] * n for _ in range(n)]
for _ in range(m):
    i, j = list(map(int, input().split()))
    connects[i - 1].append(j - 1)
    connects[j - 1].append(i - 1)
stack = deque([0, ])
visited = [-1] * n
while stack:
    x = stack.popleft()
    for dx in connects[x]:
        if visited[dx] == -1:
            visited[dx] = x + 1
            stack.append(dx)
        else:
            continue
print('Yes')
[print(i) for i in visited[1:]]

Submission status: Accepted

Solution code:
import queue


def bfs(index, before):
    if direct[index] != -1:
        return
    print(index, before)
    direct[index] = before
    for next in graph[index]:
        bfs(index=next, before=index)


def main():
    n, m = map(int, input().split())
    graph = [[]for i in range(n+2)]
    direct = [-1 for i in range(n+2)]
    q = queue.Queue()

    for i in range(m):
        # a,b = map(lambda x:int(x)-1,input().split())
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    q.put([1, 1])
    while q.qsize() != 0:
        index, before = q.get()
        if direct[index] == -1:
            direct[index] = before
            for next in graph[index]:
                q.put([next, index])
    print("Yes")
    for i in range(2, n+1):
        print(direct[i])

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = [-1]*N
T = [0]
while len(T)>0:
  P = T
  T = []
  for x in P:
    for e in E[x]:
      if ans[e]==-1:
        T += [e]
        ans[e] = x

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

Submission status: Accepted

Solution code:
(n, m), *e = [[*map(int, t.split())] for t in open(0)]
q = [1]
ans = [0] * -~n
node = [[] for _ in range(-~n)]
temp = set()

for i, j in e:
    node[i].append(j)
    node[j].append(i)

while q:
    for x in q:
        for y in node[x]:
            if ans[y] == 0:
                ans[y] = x
                temp.add(y)
    q = list(temp)
    temp.clear()

if 0 in ans[2:]:
    print('No')
else:
    print('Yes', *ans[2:])

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限

N,M = map(int,input().split())
concat = [ [] for i in range(N)]
que = deque([1])
check = [-1 for i in range(N)]
check[0] = 0 

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


def bfs():
    if len(que)==0:
        return
    out = que.popleft()
    for i in concat[out-1]:
        if check[i-1]==-1:
            check[i-1]=out
            que.append(i)
    bfs()

bfs()
if not -1 in check:
    print("Yes")
    for i in range(1,N):
        print(check[i])
else:
    print("No")

Submission status: Accepted

Solution code:
#n=int(input())
n,m=map(int,input().split())
#a=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(m)]

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

for i in range(m):
    ll[l[i][0]-1].append(l[i][1])
    ll[l[i][1]-1].append(l[i][0])

lt=[0 for i in range(n)]
lll=[1]
for i in range(n):
    for j in ll[lll[i]-1]:
        if (j!=1 and lt[j-1]==0):
            lll.append(j)
            lt[j-1]=lll[i]

print("Yes")
for i in range(1,n):
    print(lt[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 = [0] * (n + 1)

d=deque()
d.append(1)

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

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

Submission status: Accepted

Solution code:
(n,m),*e=[[*map(int, t.split())] for t in open(0)]
t=[[]for _ in range(n+1)]
for a,b in e:t[a]+=[b];t[b]+=[a]
q=[1]
a=[0]*-~n
while q:q=[a[j]==0and(a.__setitem__(j,i)or j)for i in q for j in t[i]]
print('Yes',*a[2:])