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:
(n,m),*t=[map(int,t.split())for t in open(0)]
e=[[]for _ in range(n+1)]
for a,b in t:
  e[a]+=b,
  e[b]+=a,
q=[1]
d=[0]*-~n
for v in q:
  for w in e[v]:
    if d[w]<1:
      d[w]=v
      q+=w,
print('Yes',*d[2:])

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:
import sys
from collections import deque

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N, M = LI()
G = [[] for _ in range(N+1)] # 隣接リスト

for _ in range(M):
    a, b = LI()
    G[a].append(b)
    G[b].append(a)

par = [None] * (N + 1)
# uからの距離
def bfs(u):
    queue = deque([u])
    d = [None] * (N+1)
    
    d[u] = 0
    while queue:
        v = queue.popleft()
        for i in G[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                par[i] = v
                queue.append(i)
    return d

d = bfs(1)
print('Yes')
print(*par[2:], sep='\n')

Submission status: Accepted

Solution code:
it = input()
it = it.split()
n = int(it[0])
m = int(it[1])
p = [[] for _ in range(n)]
for _ in range(m):
    itf = input()
    itf = itf.split()
    a = int(itf[0])
    b = int(itf[1])
    p[a-1].append(b)
    p[b-1].append(a)
d = [1, ]
con = [0] * n
while d:
    l = d.pop(0)
    for k in p[l-1]:
        if con[k-2]==0:
            d.append(k)
            con[k-2] = l
print('Yes')
for i in range(n-1):
    print(con[i])

Submission status: Accepted

Solution code:
import collections
N, M = map(int, input().split())
G = collections.defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

dist = [-1] * (N + 1)
que = collections.deque()
 
dist[1] = 0
que.append(1)
 
while len(que):
    v = que.popleft()
    for nv in G[v]:
        if dist[nv] != -1:
            continue
        dist[nv] = v
        que.append(nv)
if -1 in dist[2:]:
    print('No')
else:
    print('Yes')
    for value in dist[2:]:
        print(value)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
d_net = {}  # dict of path
d_path = {}  # dict of return path

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

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

start_list = d_net[1]
tmp_list = []
for no in start_list:
    d_path[no] = 1
    tmp_list.append(no)

while True:
    next_list = []
    for no in tmp_list:
        for next_no in d_net[no]:
            if next_no not in d_path:
                d_path[next_no] = no
                next_list.append(next_no)
    tmp_list = next_list
    if(tmp_list == []):
        break
print("Yes", end="\n")
for i in range(2, n+1):
    print(d_path[i], end="\n")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
N, M = map(int, input().split())
C = [list(map(int, input().split())) for i in range(M)]

def bfs(now):
    plan = deque([])
    plan.append(now)
    visited[now][0] = True
    while plan:
        now = plan.popleft()
        for i in PATH[now]:
            if visited[i][0] == True:
                continue
            else:
                plan.append(i)
                visited[i][0] = True
                visited[i][1] = now

if __name__ == '__main__':
    PATH = [deque([]) for i in range(N+1)]
    
    for i in range(M):
        PATH[C[i][0]].append(C[i][1])
        PATH[C[i][1]].append(C[i][0])
    visited = [[False,0] for i in range(N+1)]
    bfs(1)
    print("Yes")
    for i in range(2,N+1):
        print(visited[i][1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
N, M = map(int, input().split())
C = [list(map(int, input().split())) for i in range(M)]

def bfs(room, now):
    # print(room, now)
    plan = deque([])
    # for r in room:
    #     plan.append(r)
    plan.append(now)
    # print(plan)
    visited[1][0] = True
    while plan:
        now = plan.popleft()
        # print(now, plan)
        for i in PATH[now]:
            if visited[i][0] == True:
                # print('true')
                continue
            else:
                # for r in PATH[next]:
                #     plan.append(r)
                plan.append(i)
                # print(plan)
                visited[i][0] = True
                visited[i][1] = now

if __name__ == '__main__':
    PATH = [deque([]) for i in range(N+1)]
    
    for i in range(M):
        PATH[C[i][0]].append(C[i][1])
        PATH[C[i][1]].append(C[i][0])
    # print(PATH)
    visited = [[False,0] for i in range(N+1)]
    bfs(PATH[1], 1)
    # print(visited)
    print("Yes")
    for i in range(2,N+1):
        print(visited[i][1])

Submission status: Accepted

Solution code:
#168D
def main():
    import sys
    
    N, M =map(int, sys.stdin.readline().split())
    AB = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
    
    edge = [[] for _ in range(N)]
    for ab in AB:
        edge[ab[0]-1] += [ab[1]-1]
        edge[ab[1]-1] += [ab[0]-1]
    
    #print(edge)
    
    L = [-1 for i in range(N)] #道標(親p)を調べる
    
    #p:親 c:子
    def bfs(p):
        from collections import deque
        queue = deque([p])
        L[p] =0
        while queue:
            p = queue.popleft()
            for c in edge[p]:
                if L[c]==-1: #-1のとき未開
                    #print(c)
                    L[c] = p+1 #道標(どこから来たか)
                    #L[c] = L[now]+1 #階層の深さ
                    queue.append(c)
        
    
    bfs(0)
    print('Yes')
    for i in L[1:]:
        print(i)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:

from collections import deque
import sys
input = sys.stdin.readline
N,M = (int(x) for x in input().split())
connection ={i:set() for i in range(1,N+1)}

#構造入力
for i in range(1,M+1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b)
    connection[b].add(a)

#幅優先探索
dq =deque()
dq.append(1)
parent ={i:-1 for i in range(1,N+1)} #1につながっている＝答え
parent[1] =0
while dq:
    now =dq.popleft()
    for next in connection[now]:
        if parent[next] !=-1:
            continue
        else:
            parent[next] =now
            dq.append(next)
if -1 not in parent.values():
    del parent[1]
    print("Yes")
    print(*parent.values(),sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

def m():
    N, M = map(int, input().split())
    g = [[] for _ in range(N + 1)]
    dp = [10 ** 9] * (N + 1)
    visited = [False] * (N + 1)
    for _ in range(M):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)


    def bfs(root):
        visited[root] = True
        dp[root] = 0
        queue = deque([])
        for q in g[root]:
            dp[q] = root
            queue.append(q)
            visited[q] = True
        while queue:
            q = queue.popleft()
            for k in g[q]:
                if not visited[k]:
                    queue.append(k)
                    dp[k] = q
                    visited[k] = True
    bfs(1)

    if not all(visited[2:]):
        print('No')
        return

    print('Yes')
    for j in dp[2:]:
        print(j)
    return

m()

Submission status: Accepted

Solution code:

def m():
    N, M = map(int, input().split())
    g = [[] for _ in range(N + 1)]
    dp = [10 ** 9] * (N + 1)
    visited = [False] * (N + 1)
    for _ in range(M):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)


    def bfs(root):
        visited[root] = True
        dp[root] = 0
        queue = []
        for q in g[root]:
            dp[q] = root
            queue.append(q)
            visited[q] = True
        while queue:
            q = queue.pop(0)
            for k in g[q]:
                if not visited[k]:
                    queue.append(k)
                    dp[k] = q
                    visited[k] = True
    bfs(1)

    if not all(visited[2:]):
        print('No')
        return

    print('Yes')
    for j in dp[2:]:
        print(j)
    return

m()

Submission status: Accepted

Solution code:
# 俺はBFSが実装できるようになる！！！
from collections import deque

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

next_v = deque([0])
INF = 10**18
# 0からの距離を保存する部分
dist = [INF]*n
dist[0] = 0
# 1からnまででどこからきたのか記述する
prev = [-1]*n
while next_v:
    v1 = next_v.popleft()
    for v2 in edges[v1]:
        if dist[v2] != INF:
            continue
        dist[v2] = dist[v1] + 1
        prev[v2] = v1
        next_v.append(v2)

if min(prev[1:]) == -1:
    print('No')
else:
    print('Yes')
    ans = [x+1 for x in prev[1:]]
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
d = deque()
shirube = [0 for _ in range(n+1)]
road = [[] for _ in range(n+1)]
for i in range(m):
    r1, r2 = map(int, input().split())
    road[r1].append(r2)
    road[r2].append(r1)
for node in road[1]:
    d.append(node)
    shirube[node] = 1
while len(d) != 0:
    node = d.popleft()
    for next_node in road[node]:
        if shirube[next_node] == 0:
                d.append(next_node)
                shirube[next_node] = node 
print('Yes')
shirube_ans = shirube[2:n+1]
for s in shirube_ans:
    print(s)

Submission status: Accepted

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

YES = "Yes"  # type: str


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    edges = defaultdict(list)
    for i in range(M):
        edges[A[i] - 1].append(B[i] - 1)
        edges[B[i] - 1].append(A[i] - 1)
    queue = deque()
    queue.append(0)
    before_node = [None] * N
    while queue:
        node = queue.popleft()
        for next_node in edges[node]:
            if before_node[next_node] is None:
                queue.append(next_node)
                before_node[next_node] = node + 1
    print("Yes")
    print("\n".join(map(str, before_node[1:])))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
edges = [[]for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)

next_v = deque([0])
prev = [-1]*n
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if prev[v2] != -1:
            continue
        prev[v2] = v+1
        next_v.append(v2)

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

Submission status: Accepted

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

print("Yes");
n, m = [int(x) for x in input().split()] # nは頂点の数、mは辺の数
g = [[] for _ in range(n)] # 隣接リスト

for _ in range(m):
    aa, bb = [int(x) for x in input().split()]
    a = aa-1;
    b = bb-1;
    g[a].append(b)
    g[b].append(a)

from collections import deque

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


baka = 1;

while baka <= n-1:
    aho = len(g[baka]); #ahoはつながっている通路の個数
    manuke = 0;
    while manuke <= aho-1:
        xx = d[g[baka][manuke]];
        if xx == d[baka] - 1:
            print(g[baka][manuke]+1);
            break;
        manuke = manuke + 1;
    
    baka = baka + 1;

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans = [-1]*(n+1)
que = deque([1])

while que:
    q = que.popleft()
    for i in ab[q]:
        if ans[i] == -1:
            que.append(i)
            ans[i] = q

print("Yes")

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ways = [list(map(int, input().split())) for _ in range(m)]
graph = [[] for _ in range(n)]
for way in ways:
    graph[way[0]-1].append(way[1]-1)
    graph[way[1]-1].append(way[0]-1)
dist = [-1 for _ in range(n)]
dist[0] = 0
que = []
que.append(0)
while (len(que) > 0):
    v = que.pop(0)
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        que.append(i)
print('Yes')
for i in range(1, n):
    for j in graph[i]:
        if dist[j] == dist[i] - 1:
            print(j+1)
            break

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())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
# print(graph)

res = [-1] * (N)
que = deque()
que.append(0)

while que:
    i = que.popleft()
    for j in graph[i]:
        if res[j] == -1:
            res[j] = i
            que.append(j)

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

Submission status: Accepted

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

def bfs(x):
    q = deque([])
    q.append(x)
    ans[1]=1
    while len(q)>0:
        pos = q.popleft()
        
        for i in edge[pos]:
            if ans[i] == 0:
                q.append(i)
                ans[i] = pos
    return ans

ans = bfs(1)
#print(ans)
ans.pop(0)
if 0 in ans:
  print("No")
else:
  print("Yes")
  for i in range(1,len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

tmp = input().split()
N = int(tmp[0])
M = int(tmp[1])
ve = [deque() for _ in range(N)]
todo = deque()

s = 0
for m in range(M):
    S, T  = map(int,input().split())
    ve[S-1].append(T)
    ve[T-1].append(S)

visited = [False]*N
dist = [0]*N
todo.append(1)
   
while len(todo)>0:
    now = todo.popleft()   
    while len(ve[now-1])>0:
        sr = ve[now-1].pop()
        if  visited[sr-1]: continue
        dist[sr-1] = now
        visited[sr-1] = True
        todo.append(sr)

print('Yes')
[print(i) for i in dist[1:]]

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A, B = [0]*M, [0]*M

to = {i: [] for i in range(N)}

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

q = []
dist = [-1]*N
dist[0] = 0
pre = [-1]*N
q.append(0)
while len(q)>0:
    v = q.pop(0)
    for u in to[v]:
        if dist[u]==-1:
            dist[u] = dist[v]+1
            pre[u] = v
            q.append(u)
print("Yes")
print(*map(lambda x:x+1, pre[1:]), sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

N, M=map(int,input().split())
A=[""]*(N+1)
S=[[] for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    #A[int(a)]=A[int(a)]+b
    #A[int(b)]=A[int(b)]+a
    #print(A)
    S[a].append(b)
    S[b].append(a)

ans = [-1] * (N + 1)
que = deque([1])

while len(que) != 0:
    q = que.popleft()
    for i in S[q]:
        if ans[i] == -1: 
            que.append(i)
            ans[i] = q

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

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int, input().split())
c = [[] for i in range(n)]
d = [-1 for i in range(n)]
d[0] = 0

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

# 部屋 1 をキューに入れる
que = deque([])
que.append(0)

while que:
    # キューの先頭を取り出す
    p = que.popleft()
    # 今いる部屋と繋がっている部屋を順番に探索
    for i in c[p]:
        # すでに訪れたことがあるかの判定
        if d[i] != -1:
            continue
            # 移動できるならキューに入れ、その部屋の道しるべを p で確定する
        que.append(i)
        d[i] = p

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

Submission status: Accepted

Solution code:
import queue
N,M=map(int,input().split())
adj=[[] for i in range(N+1)]
parent=[-1] * (N+1)
for m in range(M):
    a,b=map(int,input().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:]:
    print(p)

Submission status: Accepted

Solution code:
import queue

n, m = map(int, input().split())
table = [[] for i in range(n+1)]
ans = [(1e9, 0) for i in range(n+1)]
seen = [False for _ in range(n+1)]
seen[1] = True

for i in range(m):
    a, b = map(int, input().split())
    # print(table[min(a, b)])
    # table[min(a, b)].append(max(a, b))
    table[a].append(b)
    table[b].append(a)

q = queue.Queue()

q.put((1, table[1]))
while(not q.empty()):
    element = q.get()
    for i in element[1]:
        if seen[i]:
            continue
        ans[i] = element[0]
        seen[i] = True
        q.put((i, table[i]))


if 1e9 in ans[2:]:
    print("No")
else:
    print("Yes")
    for i in ans[2:]:
        print(i)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]


n,m = imap()
g = [[] for i in range(n+1)]
for i in range(m):
    a,b = imap()
    g[a].append(b)
    g[b].append(a)

q = col.deque([1])
know = barr(n+1); know[1] = True
anss = iarr(n+1)
while q:
    now = q.popleft()
    for next in g[now]:
        if know[next]: continue
        else: know[next] = True; q.append(next); anss[next] = now

print("Yes")
for ans in anss[2:]: print(ans)

Submission status: Accepted

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


Visited = [False for i in range(n)]
depth = [0 for i in range(n)]
q = deque()
q.append(0)
while q:
    st = q.popleft()
    for i in Map[st]:
        if Visited[i]==True:
            continue
        depth[i] = depth[st]+1
        Visited[i] = True
        q.append(i)
ans = []
depth[0] = 0
for i in range(1,n):
    for j in Map[i]:
        if depth[i]-1==depth[j]:
            ans.append(j+1)
            break

if len(ans)==0:
    print('No')
else:
    print('Yes')
    for i in ans:
        print(i)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

#標準入力
n,m = imap()
ab = np.array([iarr() for i in range(m)])
a,b = ab.T[0]-1, ab.T[1]-1

#隣接行列はnumpy使うな
g = [[] for i in range(n)]
for aa,bb in zip(a,b):
    g[aa].append(bb)
    g[bb].append(aa)


anss = [0]*n
know = [0]*n; know[0] = 1
q = col.deque([0])
while q:
    now = q.popleft()
    for next in g[now]:
        if know[next]: continue
        else: know[next] = 1; anss[next] = now; q.append(next)

print('Yes')
for ans in anss[1:]: print(ans+1)

Submission status: Accepted

Solution code:
import collections

N, M = map(int, input().split(' '))
edges = {i: [] for i in range(N)}
depth = [-1 for i in range(N)]
ans = []

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

depth[0] = 0
que = collections.deque()
que.append((0, -1))
while que:
    now, par = que.popleft()
    for edge in edges[now]:
        if edge == par or depth[edge] != -1:
            continue
        depth[edge] = depth[now] + 1
        que.append((edge, now))

for i in range(1, N):
    for edge in edges[i]:
        if depth[edge] < depth[i]:
            ans.append(edge + 1)
            break

print('Yes')
print('\n'.join([str(a) for a in ans]))

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
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)

# BFS
reach = [False] * N
prev_v = [-1] * N
que = deque()

reach[0] = True
que.append(0)
while que:
    v = que[0]
    que.popleft()
    for new_v in graph[v]:
        if reach[new_v]:
            continue
        que.append(new_v)
        reach[new_v] = True
        prev_v[new_v] = v

for i in range(N):
    if not reach[i]:
        print("No")
        exit()
print("Yes")
for i in range(1, N, 1):
    print(prev_v[i]+1)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n, m = map(int, input().split())
    paths = [[] for i in range(n)]
    dist = [-1] * n

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

    next = []
    # next is (from, to)
    for i in paths[0]:
        next.append((0, i))

    for prev, to in next:
        if dist[to] == -1:
            dist[to] = prev
            for i in paths[to]:
                next.append((to, i))

    if dist.count(-1) != 0:
        print("No")
    else:
        print("Yes")
        for i in range(1, n):
            print(dist[i] + 1)

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int,input().split())
G = [[] for _ in range(N+1)]
dist = [-1] * (N+1)
pre = [1] * (N+1)
dist[0:2] = [0,0]
q = deque()

for i in range(M):
    A,B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)
#print(G)    
q.append(1)
while q:
    v = q.popleft()
    for i in G[v]:
        if dist[i] != -1:
            continue
        dist[i] = pre[v] + 1
        pre[i] = v
        q.append(i)
print("Yes")
for i in range(2,N+1):
    print(pre[i])

Submission status: Accepted

Solution code:

from collections import deque

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

# グラフをリストとして表現する
G = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

# 原点1からの距離を記録する
d = [0] + [-1] * (N-1)

que = deque()
que.append(0)

while que:
    p = que.popleft()
    for v in G[p]:
        if d[v] < 0:
            d[v] = p+1
            que.append(v)


if min(d[1:]) < 0:
    print('No')
else:
    print('Yes')
    for g in d[1:]:
        print(g)

Submission status: Accepted

Solution code:
import math

def solve():
    ans = [-1 for i in range(n+1)]
    remaining = set(range(1, n+1))
    remaining.remove(1)
    last_visited = [1]
    last_visited2 = []
    while remaining:
        c = len(remaining)
        for r in last_visited:
            for ad in adj[r]:
                if ad in remaining:
                    last_visited2.append(ad)
                    remaining.remove(ad)
                    ans[ad] = r
        last_visited = last_visited2
        last_visited2 = []
        if len(remaining) == c:
            print("No")
            return
    print("Yes")
    for i in ans[2:]:
        print(i)
    return

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

Submission status: Accepted

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

from collections import deque


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

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

ANS = [0] * (n + 1)
SEARCHED = [False] * (n + 1)

SEARCHED[1] = True
QUEUE = deque([1])
while QUEUE:
    v = QUEUE.popleft()
    for w in GRAPH[v]:
        if SEARCHED[w]:
            continue
        ANS[w] = v
        SEARCHED[w] = True
        QUEUE.append(w)

print("Yes")
for ans in ANS[2:]:
    print(ans)

Submission status: Accepted

Solution code:
import math
import re
import copy

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

q = [0]
pre = [None] * n
while len(q) != 0:
    for x in to[q[0]]:
        if pre[x] != None:
            continue
        pre[x] = q[0]
        q.append(x)
    q.pop(0)

if all(pre[i] != None for i in range(n)):
    print("Yes")
    for i in range(1,n):
        print(pre[i]+1)
else:
    print('No')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
w={}
for i in range(m):
    a,b=map(int,input().split())
    if a in w: w[a].add(b)
    else: w[a]=set([b])
    if b in w: w[b].add(a)
    else: w[b]=set([a])

d=[-1]*(n+1)
p=[set([]),set([1])]
d[1]=0
f=1
while 1:
    x=f%2
    y=(x+1)%2
    for i in p[x]:
        for j in w[i]:
            if d[j]==-1 or f<d[j]:
                d[j]=f
                p[y].add(j)
    p[x]=set([])
    if len(p[y])==0: break
    f+=1
print("Yes")
for i in range(2,n+1):
    for j in w[i]:
        if d[j]+1==d[i]:
            print(j)
            break

Submission status: Accepted

Solution code:
from typing import List
N, M = map(int, input().split())
graph:List[List[int]] = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(lambda x : int(x) -1 , input().split())
    graph[a].append(b)
    graph[b].append(a)
prev = [-1]*N
prev[0] = 0
import queue
qu = queue.Queue()
qu.put(0)
while not qu.empty():
    top = qu.get()
    for nxt in graph[top]:
        if prev[nxt] == -1:
            prev[nxt] = top
            qu.put(nxt)
if all(x != -1 for x in prev[1:]):
    print("Yes")
    print("\n".join(map(lambda x : str(x+1), prev[1:])))
else :
    print("No")

Submission status: Accepted

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

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

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

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

const_vary=list()


while 1:
  const_vary=const
  const=[]
  
  while len(const_vary):
    get=const_vary.pop()
    
    for n in list_tonari[get]:
      if ans[n] ==0:
        ans[n]=get
        list_tonari[n].remove(get)
        const.append(n)
        
  if len(const)==0:
    break
    
print("Yes")
for n in ans[2:]:
  print(n)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
 
from heapq import heappush, heappop
INF = float("inf")
miti = [-1]*N
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                miti[t] = v+1
                heappush(que, (dist[t], t))
    return dist
 
edge = [[] for _ in range(N)]
 
for _ in range(M):
    a,b = map(int,input().split())
    edge[a-1].append((b-1,1))
    edge[b-1].append((a-1,1))
 
dist = dijkstra(N,edge,0)
 
if -1 in miti[1:]:
    print("No")
else:
    print("Yes")
    for t in miti[1:]:
        print(t)