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 = map(int, input().split())
graph = [[] for n in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
# 入力例 1の場合
# graph : [[], [2], [1, 3, 4], [2, 4], [3, 2]] graphのインデックスが部屋名
# graph[2] : 部屋2は、1,3,4と繋がっている
# graph[4] : 部屋4は、3,2と繋がっている

# 次に探索をする部屋番号をストックしておく。まずは部屋番号1から探索を始めるので、１を入れておく
q = [1]

# ans[部屋番号]=道標が指す部屋番号とする。探索していない部屋を全て'No'として表す。道標が存在しなかった場合、'No'が残る
ans = ['No' for n in range(N + 1)]
ans[0] = 1  # 部屋番号0は存在しないのでテキトーに1を入れておく
ans[1] = 1  # 部屋番号1の道標が指す部屋番号は1になるので、最初から1を入れておく

while q:  # qの中身がなくなったらbreak
    now = q.pop(0) # 現在地を指定（キューの先頭）するとともに、qから先頭を削除する。　一番最初の現在地は1になる。
    for edge in graph[now]:
        if ans[edge] != 'No': 
            continue
        ans[edge] = now
        q.append(edge)

if not 'No' in ans:
    print('Yes')
    for n in range(2, N + 1):
        print(ans[n])
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
edge = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    
v = [-1 for i in range(n)]
v[0]=0
q = deque()
q.append(0)
while len(q) > 0:
    x = q.popleft()
    for y in edge[x]:
        if v[y]!=-1:
            continue
        q.append(y)
        v[y] = x

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

Submission status: Accepted

Solution code:
####以下カンニング####
n, m = map( int, input().split() )
connect = {}

for _ in range( m ):
    a, b = map( int, input().split() )
    try:
        connect[ a ].append( b )
    except KeyError:
        connect[ a ] = [ b ]
    try:
        connect[ b ].append( a )
    except KeyError:
        connect[ b ] = [ a ]

queue = [ 1 ]
guide = [ -1 ] * ( n+1 )
visited = [ False ] * ( n+1 )

while queue:
    x = queue.pop(0)
    for y in connect[ x ]:
        if visited[ y ] == False:
            queue.append( y )
            guide[ y ] = x
            visited[ y ] = True

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m = map(int, input().split())
graph = [0] + [[] for _ in range(n)]
for _ in range(m):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

from collections import deque

def bfs(graph, queue, dist, prev):
    while queue:
        current = queue.popleft()

        for c in graph[current]:
            if dist[c] != -1:
                continue
            dist[c] = dist[current] + 1
            prev[c] = current
            queue.append(c)

queue = deque([1])
dist = [0] + [-1] * n
dist[1] = 0
prev = [0] + [-1] * n
prev[1] = 0
bfs(graph, queue, dist, prev)
if -1 in prev:
    print('No')
else:
    print('Yes')
    for p in prev[2:]:
        print(p)

Submission status: Accepted

Solution code:
import networkx as nx
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


G = nx.Graph()
N, M = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]
G.add_edges_from(edge)
pre = nx.predecessor(G, 1)

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

Submission status: Accepted

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

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

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

res = [0]*(n-1)
used = [False]*n

tank = deque([0])
while tank:
    q = tank.popleft()
    if used[q]:
        continue
    used[q] = True

    for go in edge[q]:
        if go == 0 or res[go-1] != 0:
            continue
        res[go-1] = q+1
        tank.append(go)
print("Yes")
print(*res,sep='\n')

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
graph = [[] for n in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
# 入力例 1の場合
# graph : [[], [2], [1, 3, 4], [2, 4], [3, 2]] graphのインデックスが部屋名
# graph[2] : 部屋2は、1,3,4と繋がっている
# graph[4] : 部屋4は、3,2と繋がっている

#次に探索をする部屋番号をストックしておく。まずは部屋番号1から探索を始めるので、１を入れておく
q = [1]
#ans[部屋番号]=道標が指す部屋番号とする。探索していない部屋を'No'として表す。
ans = ['No' for n in range(N+1)]
ans[0] = 1
ans[1] = 1 #ans[1]
while q: #qの中身がなくなったらbreak
    # 現在地を指定（キューの先頭）するとともに、qから先頭を削除する。　一番最初の現在地は1になる。
    now = q.pop(0)
    for edge in graph[now]:
        if ans[edge] != 'No':
            continue
        ans[edge] = now
        q.append(edge)

if not 'No' in ans:
    print('Yes')
    for n in range(2,N+1):
        print(ans[n])
else:
    print('No')

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
graph = [[] for n in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
# 入力例 1の場合
# graph : [[], [2], [1, 3, 4], [2, 4], [3, 2]] graphのインデックスが部屋名
# graph[2] : 部屋2は、1,3,4と繋がっている
# graph[4] : 部屋4は、3,2と繋がっている

#次に探索をする部屋番号をストックしておく。まずは部屋番号1から探索を始めるので、１を入れておく
q = [1]
#ans[部屋番号]=道標が指す部屋番号とする。探索していない部屋を'No'として表す。
ans = ['No' for n in range(N+1)]
ans[1] = 1 #ans[1]
while q: #qの中身がなくなったらbreak
    # 現在地を指定（キューの先頭）するとともに、qから先頭を削除する。　一番最初の現在地は1になる。
    now = q.pop(0)
    for edge in graph[now]:
        if ans[edge] != 'No':
            continue
        ans[edge] = now
        q.append(edge)

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
g = [[] for i 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)
from collections import deque
d = deque([[0,0]]) # 左は今考えてる部屋、右は前の部屋
ans = [-1 for i in range(n)]
kak = [-100 for i in range(n)]
while d:
    u,v = d.popleft()
    ans[u] = v
    for j in g[u]:
        if  kak[j] == -100:
            kak[j] = 0
            d.append([j,u])
        else:
            continue
print('Yes')
for i in range(1,n):
    print(ans[i]+1)

Submission status: Accepted

Solution code:
import collections


def main():
    n, m = input_list()
    route = [[] for i in range(n)]
    for _ in range(m):
        a, b = input_list()
        route[a-1].append(b-1)
        route[b-1].append(a-1)

    next_q = collections.deque()
    flags = [-1] * n
    flags[0] = 999
    next_q.append(0)
    while next_q:
        cur = next_q.popleft()
        for room in route[cur]:
            if flags[room] == -1:
                flags[room] = cur
                next_q.append(room)

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


def input_list():
    return list(map(int, input().split()))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
TO = [[] for i in range(n)] #隣接リスト adjacency list
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b -1
    TO[a].append(b)
    TO[b].append(a)

#BFS
#変数定義
Q = deque([])
DIST = [-1 for i in range(n)]
PRE = [-1 for i in range(n)]
#初期値の設定
DIST[0] = 0
Q.append(0)
#処理
while len(Q) > 0:
    x = Q.popleft()  
    for i in range(len(TO[x])):
        y = TO[x][i]
        if DIST[y] != -1: continue
        DIST[y] = DIST[x] + 1
        PRE[y] = x
        Q.append(y)

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

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
from heapq import heappush, heappop


class BreadthFirstSearch:
    def __init__(self, num_nodes):
        self.n = num_nodes
        self.adj_list = [[] for _ in range(self.n)]

    # Edge数分回すことを想定
    def add_edge(self, start, end, undirected=True):
        self.adj_list[start].append(end)
        if undirected:
            self.adj_list[end].append(start)

    # depth = distance
    def search(self, start_node):
        order = [-1] * self.n  # a bfs ordering of each vertex
        parent = [-1] * self.n  # parent of each vertex in the bfs search tree
        depth = [-1] * self.n  # the depth of each vertex
        q = deque([(start_node, -1, 0)])  # (vertex, parent, depth)
        num = 0  # current ordering
        while len(q) > 0:
            v, p, d = q.popleft()
            if order[v] < 0:  # visited v for the first time
                order[v] = num
                parent[v] = p
                depth[v] = d
                num += 1
                for u in self.adj_list[v]:
                    if order[u] >= 0:
                        continue
                    q.append((u, v, d+1))
        return order, parent, depth


class Dijkstra:
    def __init__(self, num_nodes):
        self.n = num_nodes
        self.adj_list = [[] for _ in range(self.n)]

    # Edge数分回すことを想定
    def add_edge(self, start, end, weight=1, undirected=False):
        self.adj_list[start].append((end, weight))
        if undirected:
            self.adj_list[end].append((start, weight))

    def distance(self, start):
        # 始点から各頂点までの最短距離を格納する
        self.dist = [float('inf') for _ in range(self.n)]
        # 最短経路における, その頂点の前の頂点のIDを格納する
        self.prev = [-1 for _ in range(self.n)]
        self.dist[start] = 0
        # 各要素は，(startからある頂点vまでの仮の距離, 頂点のID)からなるタプル
        q = []
        heappush(q, (0, start))
        while len(q) != 0:
            prov_cost, src = heappop(q)
            # プライオリティキューに格納されている最短距離が, 現在計算できている最短距離より大きければ，distの更新をする必要はない
            if self.dist[src] < prov_cost:
                continue
            # 他の頂点の探索
            for val in self.adj_list[src]:
                dest, cost = val
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost  # distの更新
                    heappush(q, (self.dist[dest], dest))  # キューに新たな仮の距離の情報をpush
                    self.prev[dest] = src
        return self.dist, self.prev

    def shortest_path(self, goal):
        path = [goal]
        dest = goal
        # 終点から最短経路を逆順に辿る
        while self.prev[dest] != float('inf'):
            if self.prev[dest] == -1:
                break
            path.append(self.prev[dest])
            dest = self.prev[dest]
        return path[::-1]


def get_result(data):
    N, M = data[0]
    A = data[1:]
    solver = Dijkstra(N)
    for val in A:
        solver.add_edge(val[0]-1, val[1]-1, undirected=True)
    _, prev = solver.distance(0)
    print('Yes')
    for p in prev[1:]:
        print(p + 1)
    return None


# def get_result(data):
#     N, M = data[0]
#     A = data[1:]
#     solver = BreadthFirstSearch(N)
#     for val in A:
#         solver.add_edge(val[0]-1, val[1]-1)
#     _, parent, _ = solver.search(0)
#     print('Yes')
#     for p in parent[1:]:
#         print(p+1)
#     return None


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    get_result(data)
    # print(result)

Submission status: Accepted

Solution code:
def solve(string):
    from collections import deque
    n, m, *ab = map(int, string.split())
    p = [[] for _ in range(n)]
    for a, b in zip(*[iter(ab)] * 2):
        p[a - 1].append(b - 1)
        p[b - 1].append(a - 1)
    s, ans, d = deque([0]), [0] * n, [0] + [n] * (n - 1)
    while s:
        c = s.popleft()
        for t in p[c]:
            if d[c] + 1 < d[t]:
                d[t] = d[c] + 1
                ans[t] = c + 1
                s.append(t)
    return "Yes\n" + "\n".join(map(str, ans[1:]))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
N, M = map(int, input().split())
g = defaultdict(list)
for i in range(M):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)
que = [1]
ans = [0 for _ in range(N+1)]
while len(que)>0:
  current = que.pop(0)
  for next in g[current]:
    if ans[next] == 0:
      que.append(next)
      ans[next] = current
print('Yes')
for i in range(2,N+1):
  print(ans[i])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]

    route = defaultdict(list)
    for ab in AB:
        route[ab[0]].append(ab[1])
        route[ab[1]].append(ab[0])

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

    # BFSを使って、目印を埋めていく
    while(len(que) != 0):
        v = que.popleft()

        for nv in route[v]:
            if ans[nv-1] != -1:
                continue

            ans[nv-1] = v
            que.append(nv)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

ans = [-1] * n
queue = [0]
visited = [False] * n

############### BFS ##############
while queue:
    x = queue.pop(0)
    # print(x, tree[x])
    for g in tree[x]: # つながっている部屋を1づつ調べる
        if visited[g] == False: # 訪れていなければqueueに追加
            queue.append(g)
            if ans[g] == -1: # 方向をansに追加し、訪れ済みにする
                ans[g] = x
                visited[g] = True

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

Submission status: Accepted

Solution code:
from sys import stdin
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]


def get_result(data):
    N, M = data[0]
    A = data[1:]
    solver = Dijkstra(N)
    for val in A:
        solver.add_edge(val[0]-1, val[1]-1, 1, undirected=True)
    solver.distance(0)
    prev = solver.prev
    print('Yes')
    for p in prev[1:]:
        print(p + 1)
    return None

if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    get_result(data)

Submission status: Accepted

Solution code:
from collections import deque

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

G = [[] for i 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)

dist = [1e8 for i in range(N)]
dist[0] = 0

ans = [-1 for i in range(N)]

Q = deque()
Q.append(0)

while len(Q) > 0:
    now = Q.popleft()

    for to in G[now]:
        if(dist[now] + 1 < dist[to]):
            dist[to] = dist[now] + 1
            ans[to] = now+1
            Q.append(to)

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

Submission status: Accepted

Solution code:
from _collections import deque
n,m=map(int,input().split())
M=[[] for _ in range(n)]
ANS=[-1]*n
ANS[0]=0
for i in range(m):
    a,b=map(int,input().split())
    M[b-1].append(a-1)
    M[a-1].append(b-1)

q=deque([0])

while q:
    s=q.popleft()
    for x in M[s]:
        if ANS[x]!=-1:
            continue
        q.append(x)
        ANS[x]=s
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())
ary = []
a = []
b = []
ary = [0 for i in range(n)]
chk = [False for i in range(n)]
d = {}
for i in range(m):
	aa, bb = map(int, input().split())
	if aa not in d:
		d[aa] = []
	d[aa].append(bb)
	if bb not in d:
		d[bb] = []
	d[bb].append(aa)

visited = [-1 for i in range(n)]
visited[0] = 0
queue = deque([1])
while queue:
	c = queue.popleft()
	for i in d[c]:
		if visited[i-1] != -1:
			continue
		visited[i-1] = c
		queue.append(i)
for i in visited:
	if i == -1:
		print ("No")
		exit()
print ("Yes")
for i in visited[1:]:
	print (i)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
n , m = map(int , input().split())
g = defaultdict(list)
for i in range(m):
	u , v = map(int , input().split())
	g[u].append(v)
	g[v].append(u)
#print(g)
visited = [False]*(n+1)
a = [10**10]*(n+1)
q = deque()
q.append(1)
while q:
	node = q.popleft()
	visited[node] = True
	for ele in g[node]:
		if not visited[ele]:
			if a[ele] != 10**10: 
				continue
			a[ele] = node
			q.append(ele)
#print(ans)
#print(a)
print("Yes")
for i in a[2:]:
	print(i)

Submission status: Accepted

Solution code:
import networkx as nx
n,m,*s = map(int, open(0).read().split())
 
g=nx.Graph()
g.add_nodes_from([i for i in range(1,n+1)])
for x in zip(*[iter(s)] * 2):
    g.add_edge(x[0],x[1])
di=nx.predecessor(g,source=1)
 
if len(di)!=n:
    print("No");exit()
print("Yes")
for x in range(2,n+1):
    print(di[x][0])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
map_li = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    map_li[a].append(b)
    map_li[b].append(a)
 
ans_li = [-1]*n
queue=[0]
visited = [False]*n
 
while queue:
    x = queue.pop(0)
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int,input().split())
A=[0]*M
B=[0]*M
#隣接リスト
graph=[[] for i in range(N+1)]
d=[0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    #無向グラフなので両方書く
    graph[A[i]].append(B[i])
    graph[B[i]].append(A[i])

#幅優先
def BFS(top):
    queue = deque([top])
    dist = [-1]*(N+1)#未発見の頂点なら-1、それ以外は0に向かうための次に隣接する頂点番号を格納。ただしdist[1]=0
    dist[1]=0

    queue.extend(graph[top])#頂点1(top)と隣接する頂点を全てキューに追加
    
    while(queue):
        Now_vertex = queue.popleft()
        
        for j in range(len(graph[Now_vertex])):
            if(dist[graph[Now_vertex][j]]==-1):
                queue.append(graph[Now_vertex][j])
                dist[graph[Now_vertex][j]]=Now_vertex
            
    print("Yes")
    for i in range(2,len(dist)):
        print(dist[i])
    
        
    return



BFS(1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import deque
 
N, M = map(int, input().split())
G = [[] for i 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)
q = deque()
done = [-1]*N
done[0] = 1
q.appendleft(0)
while q:
    now = q.pop()
    for to in G[now]:
        if done[to] != -1: continue
        done[to] = now+1
        q.appendleft(to)
print("Yes")
print(*done[1:], sep="\n")

Submission status: Accepted

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

ans_li = [-1]*n
queue=[0]
visited = [False]*n

while queue:
    x = queue.pop(0)
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)

Submission status: Accepted

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

ans_li = [-1]*n
queue=[0]
visited = [False]*n

while queue:
    x = queue.pop(0)
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
N,M = [int(i) for i in input().split()]
roads = [[] for _ in range(N+1)]
for _ in range(M):
    A,B = [int(i) for i in input().split()]
    roads[A].append(B)
    roads[B].append(A)
places = [0]*(N+1)
places[1] = 1
q = deque([1])
vis = [False]*(N+1)
vis[1] = True
while q:
    now = q.popleft()
    L = roads[now]
    for j in L:
        if vis[j]:
            continue
        vis[j] = True
        places[j] = now
        q.append(j)

print("Yes")
s = "\n".join(map(str, places[2:]))
print(s)

Submission status: Accepted

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

next_vec = [0]
visited = [1] + [0] * (N-1)
parent = [-1] + [0] * (N-1)
flag = 1


while next_vec:
    current_vec = next_vec[:]
    next_vec = []
    while current_vec:
        u = current_vec.pop()
        visited[u] = 1
        for v in path[u]:
            if visited[v] == 0:
                visited[v] = 1
                parent[v] = u
                next_vec.append(v)

ans_flag = 1
for i in visited:
    if i == 0:
        ans_flag = 0
if ans_flag:
    print('Yes')
    for i in range(1,N):
        print(parent[i]+1)
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import deque

def bfs2(g,n,m):
    pre=[0 for _ in range(n+1)]
    pre[1]=1
    q=deque([1])
    while q:
        x=q.popleft()
        for i in range(len(g[x])):
            if pre[g[x][i]]==0:
                q.append(g[x][i])
                pre[g[x][i]]=x
    return pre

def main2():
    #normal input
    n,m=map(int,input().strip().split())
    g=[[] for _ in range(n+1)]
    for _ in range(m):
        a,b=map(int,input().strip().split())
        g[a].append(b)
        g[b].append(a)
        
    pre=bfs2(g,n,m)
    
    print("Yes" if 0 not in pre[1:] else "No")
    for i in range(2,len(pre)):
        print(pre[i])

if __name__=="__main__":
    main2()

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
l = [[] for i in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    l[a].append(b)
    l[b].append(a)
ans = [0] * (n + 1)
f = [0] * (n + 1)
d = deque()
d.append(1)
while len(d) > 0:
    k = d.popleft()
    f[k] = 1
    for i in l[k]:
        if f[i] == 1:
            continue
        ans[i] = k
        d.append(i)
        f[i] = 1
for i in range(2, n + 1):
    if ans[i] == 0:
        print("No")
        exit()
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())
g = [[] for _ in range(n)]

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

q = deque([0])
d = [-1] * n
d[0] = 0
ans = [0] * n

print('Yes')
while q:
    p = q.popleft()
    for node in g[p]:
        if d[node] == -1:
            d[node] = d[p] + 1
            q.append(node)
        else:
            if d[node] + 1 == d[p]:
                ans[p] = node + 1
for i in range(1, n):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
N,M=list(map(int,input().split()))
AB=[set() for i in range(N+1)]
room=[0]*(N+1)
pre=[None]*(N+1)
def bfs(i):#１に到達
    Done=set()
    Done.add(i)
    d=deque([i])
    # child=set()
    # child.add(i)
    # count=1
    while(d):
        k=d.popleft()
        # if k not in child:
        #     count+=1
        #     child=child.union(Done)
        # room[k]=count
        for i in AB[k]:
            if i not in Done:
                pre[i]=k
                Done.add(i)
                d.append(i)





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

flag=True
bfs(1)
if pre.count(None)<=N+1:
    for i in range(2,N+1):
        if flag:
            print("Yes")
            flag=False
        if pre[i] is not None:
            print(pre[i])
else:print("No")

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque

N, M = map(int, input().split())
route = defaultdict(set)
for i in range(M):
    A_i, B_i = map(int, input().split())
    route[A_i].add(B_i)
    route[B_i].add(A_i)

q = deque()
q.append(1)
seen = [-1] * (N + 1)
seen[0], seen[1] = 0, 0

while len(q) > 0:
    now = q.popleft()
    for i in route[now]:
        if seen[i] == -1:
            q.append(i)
            seen[i] = now

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

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    A[i], B[i]= map(int, input().split())
links = [[] for _ in range(N + 1)]
for i in range(len(A)):
    links[A[i]].append(B[i])
    links[B[i]].append(A[i])
    
#print(links)
result = [-1] * (N + 1)
q = deque([1])
#print(q)
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
            #print(q)
print('Yes')
print('\n'.join(str(i) for i in result[2:]))

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools
import copy
from collections import deque

n, m = map(int, input().split())
g = [[] for i 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)


a = [-1]*n
d = deque([0])
while d:
    f = d.popleft()
    for i in g[f]:
        if a[i] == -1:
            a[i] = f
            d.append(i)

print("Yes")
for i in range(1,n):
    print(a[i]+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(int,input().split())
  a-=1
  b-=1
  g[a].append(b)
  g[b].append(a)
q=deque([0])
d=[-1]*n
d[0]=1
while q:
    now = q.pop()
    for i in g[now]:
        if d[i] != -1: continue
        d[i] = now+1
        q.appendleft(i)
print("Yes")
print(*d[1:], sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
AB = [map(int, input().split()) for _ in range(M)]
#print(AB)
links = [[] for _ in range(N + 1)]
for a, b in AB:
    links[a].append(b)
    links[b].append(a)
#print(AB)
#print(links)
result = [-1] * (N + 1)
q = deque([1])
#print(q)
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
            #print(q)
print('Yes')
print('\n'.join(str(i) for i in result[2:]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
d = {1:0}
q = [1]
for i in q:
    for j in g[i]:
        if j not in d:
            d[j] = i
            q.append(j)
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())
to = [[] for _ in range(N)]

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

route = deque([0])
dist = [0]*N
prev = [-1]*N

while route:
    v = route.popleft()
    for u in to[v]:
        if dist[u]: continue
        dist[u] = dist[v]+1
        prev[u] = v
        route.append(u)

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

Submission status: Accepted

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

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

for _ in range(M):
    Ai, Bi = map(int, input().split())
    memo[Ai].append(Bi)
    memo[Bi].append(Ai)

# print(memo)

visited = [False] * (N+1)
visited[1] = True
ans = [0]*(N+1)

queue = [1]

while queue:
    room = queue.pop(0)
    for connected_room in memo[room]:
        # print(connected_room)
        if visited[connected_room] == True:
            continue
        ans[connected_room] = room
        visited[connected_room] = True
        queue.append(connected_room)
print("Yes")
for a in ans[2:]:
    print(a)