Problem:


Score: 400 points

Problem Statement

There is a cave.

The cave has N rooms and M passages. The rooms are numbered 1 to N, and the passages are numbered 1 to M. Passage i connects Room A_i and Room B_i bidirectionally. One can travel between any two rooms by traversing passages. Room 1 is a special room with an entrance from the outside.

It is dark in the cave, so we have decided to place a signpost in each room except Room 1. The signpost in each room will point to one of the rooms directly connected to that room with a passage.

Since it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room 1.

If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible.

Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 2 \times 10^5

1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)

A_i \neq B_i\ (1 \leq i \leq M)

One can travel between any two rooms by traversing passages.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

If there is no way to place signposts satisfying the objective, print No.

Otherwise, print N lines. The first line should contain Yes, and the i-th line (2 \leq i \leq N) should contain the integer representing the room indicated by the signpost in Room i.

Sample Input 1

4 4
1 2
2 3
3 4
4 2

Sample Output 1

Yes
1
2
2

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

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

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

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

Thus, the objective is satisfied.

Sample Input 2

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

Sample Output 2

Yes
6
5
5
1
1

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



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


Sample output:
Yes
1
2
2

Submission status: Accepted

Solution code:
import queue
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)
    graph[b-1].append(a)
ans = [0]* n
q = queue.deque()
q.append(1)
while q:
    tmp = q.popleft()
    for i in graph[tmp-1]:
        if ans[i-1] == 0:
            q.append(i)
            ans[i-1] = tmp
                
if 0 in ans:
    print('No')
        
else:
    print('Yes')
    for i in range(1,n):
        print(ans[i])

Submission status: Accepted

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

l = [[] for i in range(n)]
for pi in ab:
    l[pi[0]-1].append(pi[1]-1)
    l[pi[1]-1].append(pi[0]-1)

ans=[0]*n

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in l[v]:
            if d[i] is None:
                ans[i] = v
                d[i] = d[v] + 1
                queue.append(i)

    for i in range(1,n):
        print(ans[i]+1)
    # return d
print('Yes')
d = bfs(0)

Submission status: Accepted

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

# 幅優先探索
def bfs(u):
    ans = [None] * (N+1)
    queue = deque([u])
    d = [None] * (N+1) # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                ans[i] = v
                queue.append(i)
    return ans
d = bfs(1)
print("Yes")
for i in range(2,N+1):
    print(d[i])

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
a=[tuple(map(int,input().split())) for i in range(m)]
pr=[[] for i in range(n)]
for i in a:
    pr[max(i)-1].append(min(i))
    pr[min(i)-1].append(max(i))
d=deque([1])
checked=[0]*n
checked[0]=1
ans=[0]*(n-1)
while len(d)>0:
    rm=d.popleft()
    for i in pr[rm-1]:
        if checked[i-1]==0:
            d.append(i)
            checked[i-1]=1
            ans[i-2]=rm
    #print(d)
print('Yes')
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import queue
import sys
n, m = list(map(int, input().split()))
a, b = zip(*[list(map(int, input().split())) for i in range(m)])

next0 = [[] for i in range(n+1)]
for i in range(m):
    x = min(a[i], b[i])
    y = max(a[i], b[i])
    next0[x].append(y)
    next0[y].append(x)

#print(next0)
#sys.exit()

def search():
    d = [0] * (n+1)
    z = [-1] * (n+1)

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

    while not que.empty():
        p = que.get()
        for nx in next0[p]:
            #print(nx)
            if 1 <= nx <= n and d[nx] == 0:
                que.put(nx)
                d[nx] = d[p] + 1
                z[nx] = p
    return d, z

z = search()[1]

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import deque

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,m = na()
    path = [[] for _ in range(n)]
    ans = [0] + [-1 for i in range(n-1)]
    sumcheck = 1
    for _ in range(m):
        a,b = na()
        a -= 1
        b -= 1
        path[a] += [b]
        path[b] += [a]
    d = deque([0])
    while len(d):
        now = d.popleft()
        for nxt in path[now]:
            if ans[nxt] == -1:
                ans[nxt] = now
                sumcheck += 1
                d.append(nxt)
    if sumcheck == n:
        print('Yes')
        for i in ans[1:]:
            print(i+1)
    else:
        print('No')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from queue import Queue

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

dict = {}

for i in range(M):
    A,B = list(map(int, input().split()))

    if A in dict:
        l = dict[A]
        l.append(B)
        dict[A] = l
    else:
        l = [B]
        dict[A] = l

    if B in dict:
        l = dict[B]
        l.append(A)
        dict[B] = l
    else:
        l = [A]
        dict[B] = l

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

ans = [-1] * N
while not queue.empty():
    tmp = queue.get()

    if tmp in dict:
        next = dict[tmp]
        for i in next:
            if ans[i - 1] == -1:
                queue.put(i)
                ans[i - 1] = tmp
        
    prev = tmp

if -1 in ans:
    print("No")
else:
    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())
neib = {i+1:[] for i in range(N)}
for i in range(M):
  a, b = map(int, input().split())
  neib[a].append(b)
  neib[b].append(a)
#print(neib)
mitishil = {i+1:-1 for i in range(1,N)}
#print(mitishil)

q = deque()
q.append(1)
while(q):
  v = q.popleft()
  ls = neib[v]
  #print(v,ls)
  for l in ls:
    #print(l)
    if (l == 1): continue
    if (mitishil[l] == -1):
      mitishil[l] = v
      q.append(l)
    #print(mitishil)
print("Yes")
for i in mitishil.values():
  print(i)

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
N, M = map(int, readline().split())
G = [[] for _ in range(N)]
E = [0] * N
for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    E[a] += 1
    G[b].append(a)
    E[b] += 1
pre = [[] for _ in range(N-1)]
visited = [-1] * N
L = []
q = deque([0])
visited[0] = 0
while q:
    x = q.popleft()
    for a in G[x]:
        if visited[a] == -1:
            visited[a] = x+1
            q.append(a)
if -1 in visited:
    print('No')
else:
    print('Yes')
    print(*visited[1:], sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
path = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)
visited = [-1] * n
ans = [-1] * n
queue = deque([0])
while queue:
    pos = queue.popleft()
    visited[pos] = 1
    ll = path[pos]
    for l in ll:
        if visited[l] == -1:
            if ans[l] == -1:
                ans[l] = pos + 1
                queue.append(l)
print("Yes")
for i in range(1, n):
    print(ans[i])

Submission status: Accepted

Solution code:
def main():
    n,m = map(int,input().split())
    ab = [list(map(int,input().split())) for _ in range(m)]
    g = [[] for _ in range(n)]
    for a,b in ab:
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    
    dist = [-1]*n
    from collections import deque
    dist[0] = 0
    q = deque()
    q.append(0)
    while q:
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = v
            q.append(nv)
    
    print('Yes')
    for v in range(1,n):
        print(dist[v]+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
root=[[] for _ in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	root[a-1].append(b-1)
	root[b-1].append(a-1)
times=[0]*n
sign=[-1]*n
sign[0]=0
color=[False]*n
que=deque([0])
while que: #qが空でないのはこう表現できる
	i=que.popleft()
	if color[i]==False:
		for edge in root[i]:
			if color[edge]==False and sign[edge]==-1: #相方が親じゃなければ(親ならすでに探索済みのはず)
				sign[edge]=i
				que.append(edge)
		color[i]=True
print('Yes')
for i in range(n-1):
	print(sign[i+1]+1)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    n,m=map(int,input().split())
    root=[[] for i in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    dict={}
    for i in range(n):
        dict[i]=-1

    start=0
    check=[False]*n
    toVis=deque()
    check[start]=True
    for v in root[start]:
        toVis.append(v)
        dict[v]=start
    #   print(i,":",start)
        check[v]=True
    while len(toVis)>0:
        now=toVis.popleft()
        #print(now)
        check[now]=True
        for v in root[now]:
            if check[v]==False:
                toVis.append(v)
                dict[v]=now
            # print(i,":",now)
                check[v]=True
    #print(dict)  
    for i in range(1,n):
        if dict[i]==-1:
            print("No")
            return 0
    print("Yes")
    for i in range(1,n):
        print(dict[i]+1)         


if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import queue
n, m = map(int,input().split())
g = [[] for _ in range(n+1)]
g_cost = [ float('inf') for _ in range(n+1)]
g_ans = [ 0 for _ in range(n+1)]
for i in range(0,m):
    s,t = map(int,input().split())
    g[s].append(t)
    g[t].append(s)

q = queue.Queue()
q.put(1)
g_cost[1] = 0
while not q.empty():
    room = q.get()
    for c_room in g[room]:
        if g_cost[room]+1 < g_cost[c_room]:
            g_cost[c_room] = g_cost[room]+1
            g_ans[c_room] = room
            q.put(c_room)
# print(g_cost)
# print(g_ans)
print("Yes")
for i in range(2,n+1):
    print(g_ans[i])

Submission status: Accepted

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

ans = [0] * (n + 1)
ans[1] = -1
queue = deque()
for s in table[1]:
    ans[s] = 1
    # 注目してるノード番号, ひとつ前の番号
    queue.append((s, 1))
while len(queue) > 0:
    node = queue.popleft()
    for t in table[node[0]]:
        if ans[t] != 0 or t == 0:
            continue
        ans[t] = node[0]
        queue.append((t, node[0]))
if 0 in ans[2:]:
    print("No")
else:
    print("Yes")
    for a in ans[2:]:
        print(a)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
ans_list = [0]*(n+1)

class Node:
    def __init__(self, x):
        self.val = x
        self.adj = []

nodelist = [Node(0)]
for i in range(1, n+1):
  nodelist.append(Node(i))

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

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

while len(q) > 0:
    node = q.popleft()

    if node is not None:
        for i in node.adj:
            if ans_list[i] == 0:
                ans_list[i] = node.val
                q.append(nodelist[i])

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

Submission status: Accepted

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

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

if len(root) != n:
    print('No')
    sys.exit()

r = sorted(root.items())
mae = [ -1 for _ in range(n)]
mae[0] = n
q = [0]
while True:
    l = len(q)
    if l == 0: break
    for i in range(l):
        ima = q[i]
        for tugi in r[ima][1]:
            if tugi == mae[ima]: continue
            if mae[tugi] != -1:
                if mae[tugi] != ima: continue
            mae[tugi] = ima
            q.append(tugi)
    q = q[l:]
if min(mae) == -1:
    print('No')
    sys.exit()
print('Yes')
for x in mae[1:]:
    print(x + 1)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
# 目印置くリスト
me = [0 for _ in range(n+1)]
me[1] = 1
miti = [[] for _ in range(n+1)]
tansaku = [0 for i in range(n+1)]
tansaku[1]=1
for i,j in l:
  miti[j].append(i)
  miti[i].append(j)
a = deque()
for i in miti[1]:
  a.append(i)
  me[i] = 1
  tansaku[i]=1
while len(a)!=0:
#  print(a)
  w = a.popleft()
  for j in miti[w]:
    if tansaku[j]==0 :
          a.append(j) 
          tansaku[j] = 1
          me[j] = w
 # print(w,tansaku,me,a)
  
print("Yes")
for i in range(len(miti)-2):
  print(me[i+2])

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
from queue import deque
setrecursionlimit(10 ** 7)

n,m = map(int,stdin.readline().rstrip().split())
li = [[]for _ in range(n)]
lin = []

length = {}
length_path = [0]*n

for i in range(m):
    a,b = map(int,stdin.readline().rstrip().split())
    a -= 1
    b -= 1
    li[a].append(b)
    li[b].append(a)
    if a < b:
        length[(a,b)] = 1
    else:
        length[(b,a)] = 1
    lin.append([a,b])


work_queue = deque([])
visited = [False]*n
work_queue.append(0)
while work_queue:
    now = work_queue.popleft()
    visited[now] = True
    for i in li[now]:
        if visited[i]:
            continue
        work_queue.append(i)
        visited[i] = True
        if now < i:
            length_path[i] = length_path[now]+length[(now,i)]
        else:
            length_path[i] = length_path[now]+length[(i,now)]
kotae = [0]*n

for num,i in enumerate(li):
    ima = i
    now = 10**10
    for j in ima:
        if length_path[j] < now:
            now = length_path[j]
            k = j
    kotae[num] = k+1
print("Yes")
for i in kotae[1:]:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log,sin,cos
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
n,m=mii()

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

#前の場所がどこだったか
ans=[-1]*n

for i in range(m):
    a,b=mii()
    mat[a-1].append([a-1,b-1])
    mat[b-1].append([b-1,a-1])


q=deque(mat[0])
#print(q,ans[1])
while len(q)>0:

    node = q.popleft()
    #print(node[1],111,type(node[1]),mat[node[1]])
    if node is not None:
        if ans[node[1]]==-1:
            ans[node[1]]=node[0]
            for i in mat[node[1]]:
                q.append([node[1],i[1]])

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

Submission status: Accepted

Solution code:
from collections import defaultdict
def D():
    N, M = map(int, input().split())
    edges = defaultdict(list)
    for i in range(M):
        A, B = map(int, input().split())
        edges[A].append(B)
        edges[B].append(A)
    
    ans = {}
    q = [(1, None)]
    seen = set(q)
    while q:
        cur, last = q.pop(0)
        ans[cur] = last
        for room in edges[cur]:
            if room not in seen:
                q.append((room, cur))
                seen.add(room)
    
    if len(ans) < N:
        print('No')
    else:
        print('Yes')
        for i in range(2, N+1):
            print(ans[i])

D()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
d = {i:set([]) for i in range(1,n+1)}
e={i:0 for i in range(1,n+1)}
s={i for i in range(1,n+1)}
for _ in range(m):
    a,b = map(int,input().split())
    d[a]|={b}
    d[b]|={a}
    s-={a,b}
if len(s)!=0:
    print("No")
else:
    print("Yes")
    s={1}
    while(n>0):
        t=set([])
        for i in s:
            for j in d[i]:
                if e[j]==0:
                    e[j]=i
                    t|={j}
                    n-=1
        s=t
    for k,v in e.items():
        if k>1:
            print(v)

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue
d = defaultdict(list)
n,m = [int(i) for i in input().split()]
q=  queue.Queue()
for i in range(m):
    a,b =[int(i) for i in input().split()]
    d[a].append(b)
    d[b].append(a)
l = n-1
arr = [0]*(n+2)
#print(d)
for i in d[1]:
    if arr[i]==0:
        q.put(i)
        arr[i]=1
        l-=1
    
while(not(q.empty())):
    k = q.get()
    for i in d[k]:
        if arr[i]==0 and i!=1:
            arr[i]=k
            q.put(i)
            l-=1
    if l==0:
        break
if l==0:
    print('Yes')
    for i in range(2,n+1):
        print(arr[i])
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import deque

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

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

for a, b in ab:
    g[a].append(b)
    g[b].append(a)

temp = deque([[1, 0]])
visited = [-1] * (N+1)
visited[0] = 0
visited[1] = 0

while temp:
    q = temp.popleft()
    for i in g[q[0]]:
        if visited[i] == -1:
            temp.append([i, q[1]+1])
            visited[i] = q[0]
if -1 in visited: print('No')
else:
    print('Yes')
    for i in visited[2:]:
        print(i)

Submission status: Accepted

Solution code:
import queue

def resolve():
    n,m = map(int, input().split())
    signs = [0]*(n+1)
    maps = {}
    for _ in range(m):
        a,b = map(int, input().split())
        if a in maps.keys():
            maps[a].append(b)
        else:
            maps[a] = [b]

        if b in maps.keys():
            maps[b].append(a)
        else:
            maps[b] = [a]

        # if a < b:
        #     if a in maps.keys():
        #         maps[a].append(b)
        #     else:
        #         maps[a] = [b]
        # else:
        #     if b in maps.keys():
        #         maps[b].append(a)
        #     else:
        #         maps[b] = [a]
    
    remain = set(list(range(1, n+1)))
    q = queue.Queue()
    q.put(1)
    
    while q.empty() == False:
        curr = q.get()
        for i in maps[curr]:
            if signs[i] != 0:
                continue
            signs[i] = curr
            remain.remove(i)
            q.put(i)
    
    if len(remain) == 0:
        signs[1] = 'Yes'
        for i in range(len(signs)):
            if i == 0:
                continue
            print(signs[i])
    else:
        print('No')
            

resolve()

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

def dijkstra(start,node,edge):
    d = [2*10**5] * node
    m = [0]*node
    d[start] = 0
    q = [(0,0)]
    heapify(q)
    
    while(len(q) != 0):
      ci, i = heappop(q)
      di = d[i]
      for j in edge[i]:
        if(d[j] > di+1):
          d[j] = di + 1
          heappush(q, (di+1,j))
          m[j] = i+1
    return m

def main():
    N,M = map(int, input().split())
    
    E = [[] for _ in [0]*N]
    for i in range(M):
      a,b = (int(x) for x in input().split())
      E[a-1].append(b-1)
      E[b-1].append(a-1)

    m = dijkstra(0, N, E)
    print("Yes")
    print("\n".join(map(str, m[1:])))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N,M = list(map(int, input().split()))
ab = deque([[] for i in range(N+1)])
for _ in range(M):
  A= list(map(int, input().split()))
  ab[A[0]].append(A[1])
  ab[A[1]].append(A[0])

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

stack = deque([1])

while stack:
  x = stack.pop()
  temp = deque([])
  for i in ab[x]:
    if done[i] == 0:
      done[i] += 1
      ans[i] = x
      stack.appendleft(i)

print('Yes')
for i in range(2,len(ans)):
  print(ans[i])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n, m = Is()
AB = TIR(m)
C = [set() for _ in range(n)]
for a, b in AB:
    a -= 1
    b -= 1
    C[a].add(b)
    C[b].add(a)

ANS = [INF]*n
visited = [False]*n
def bfs():
    que = deque()
    que.append(0)
    while que:
        x = que.popleft()
        visited[x] = True
        for y in C[x]:
            if not visited[y]:
                ANS[y] = x
                que.append(y)
                visited[y] = True

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

Submission status: Accepted

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

queue = deque()
pre = [-1 for _ in range(n)]
dist = [10**10 for _ in range(n)]

dist[0] = 0
queue.append(0)
while queue:
    now = queue.popleft()
    for to in G[now]:
        if dist[to] > dist[now] + 1:
            dist[to] = dist[now] + 1
            pre[to] = now
            queue.append(to)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰回数の上限を変更
from collections import deque
N,M=map(int,input().split())
G=[[]for _ in range(N)]

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

dist=[-1 for _ in range(N)]
chk=[0 for _ in range(N)]
dist[0]=0
prev=[-1 for _ in range(N)]


que=deque()
que.append((0,-1))

while(len(que)):
    v,p=que.popleft()
    for tmp in G[v]:
        if dist[tmp]!=-1:
            continue
        dist[tmp]=dist[v]+1
        prev[tmp]=v
        que.append((tmp,v))

print("Yes")
#print(dist)
for i in range(N):
    if i==0:
        continue
    print(prev[i]+1)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
path = []
for i in range(N):
  path.append([])
for i in range(M):
  t1, t2 = [int(x) for x in input().split()]
  path[t1-1].append((t1,t2))
  path[t2-1].append((t2,t1))
l = [1]
ans = [1] + [0] * (N-1)
while len(l) > 0:
  t = l.pop(0)
  for i in range(len(path[t-1])):
    if ans[path[t-1][i][1]-1] == 0:
      ans[path[t-1][i][1]-1] = t
      l.append(path[t-1][i][1])
print('Yes')
for i in range(1, N):
  print(ans[i])

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

def bfs(x, n):
  que = deque([x])
  while que:
      node = que.popleft()
      for i in range(len(Edge[node])):
          if(Val[Edge[node][i]] > Val[node]):
              Val[Edge[node][i]] = Val[node]+1
              Dir[Edge[node][i]] = node
          que.append(Edge[node][i])
      Edge[node] = []


sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N, M = map(int,input().split())
INF = N+1
#G = [["X" for i in range(N] for i in range(N)]
Dir = [0 for i in range(N)]
Val = [INF for i in range(N)]
Val[0] = 0
Edge = [[] for i in range(N)]
ans = 0

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


bfs(0,N)


print("Yes")
for i in range(N-1):
    print(Dir[i+1]+1)

Submission status: Accepted

Solution code:
from collections import deque
N, M = [int(x) for x in input().split()]
INF = 10**6
dist = [INF] * N
ans = [-1] * N
to = [set() for _ in range(N)]
for _ in range(M):
    A, B = [int(x)-1 for x in input().split()]
    to[A].add(B)
    to[B].add(A)
bfs = deque([(0, 0, -1)])
while len(bfs):
    cur, d, p = bfs.popleft()
    if d >= dist[cur]: continue
    dist[cur] = d
    ans[cur] = p
    for v in to[cur]:
        if d+1 < dist[v]:
            bfs.append((v, d+1, cur))
print('Yes')
for a in ans[1:]:
    print(a+1)

Submission status: Accepted

Solution code:
from collections import deque

R=lambda: map(int, input().split())

n, m = R()
g = [[] for _ in range(n)]
for _ in range(m):
  u, v = R()
  g[u - 1].append(v - 1)
  g[v - 1].append(u - 1)

r = [None] * (n - 1)
V = [True] + [False] * (n - 1)
q = deque([0])
while q:
  u = q.popleft()
  for v in g[u]:
    if not V[v]:
      V[v] = True
      r[v - 1] = u + 1
      q.append(v)

print(*(['No'],['Yes'] + r)[all(r)], sep='\n')

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict
import collections
import math
import sys
import queue
sys.setrecursionlimit(200000)
mod = 1000000007

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

graph = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

tf = [False] * (n + 1)
sirube = [0] * (n + 1)
def bfs(v):
    q = queue.Queue()
    q.put([v,0])
    tf[v] = True
    while not q.empty():
        sub = q.get()
        now = sub[0]
        before = sub[1]
        for next in graph[now]:
            if tf[next]:
                continue
            tf[next] = True
            if sirube[next] == 0:
                sirube[next] = now
            q.put([next, now])

bfs(1)
for i in range(2, n + 1):
    if sirube[i] == 0:
        print("No")
        exit()

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

Submission status: Accepted

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
path_d = defaultdict(list)
result = dict()

for _ in range(m):
    a, b = input().split()
    if a == "1":
        result[b] = a
    elif b == "1":
        result[a] = b
    else:
        path_d[a].append(b)
        path_d[b].append(a)

tmp = list(result.keys())

while path_d:
    tmp2 = list()
    for _a in tmp:
        for _b in path_d[_a]:
            if _b not in result:
                result[_b] = _a
                tmp2.append(_b)
        del path_d[_a]
    tmp = tmp2

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = {}
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in X:
        X[a].append(b)
    else:
        X[a] = [b]

    if b in X:
        X[b].append(a)
    else:
        X[b] = [a]

ans = [0 for _ in range(N)]
ans[0] = 1
que = [[0, X[0]]]
while len(que) > 0:
    f, targets = que.pop(0)
    for t in targets:
        if ans[t] == 0:
            ans[t] = f + 1
            que.append([t, X[t]])

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

Submission status: Accepted

Solution code:
from collections import deque

def bfs(index, ans):
    d = deque()
    ans[index] = 0
    d.append(index)
    while len(d) > 0:
        v = d.popleft()
        for node in table[v]:
            if ans[node] == -1:
                ans[node] = v
                d.append(node)
    return ans

n, m = map(int, input().split())
table = [[] for j in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    table[a-1].append(b-1)
    table[b-1].append(a-1)
ans = [-1 for i in range(n)]
ans = bfs(0, ans)
if -1 in ans:
    print('No')
else:
    print('Yes')
    for a in ans[1:]:
        print(a+1)