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: Wrong Answer

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}
    point=0
    while(n>0):
        t=set([])
        point+=1
        for i in s:
            for j in d[i]:
                if e[j]==0:
                    e[j]=point
                    t|={j}
                    n-=1
        s=t
    for k,v in e.items():
        if k>1:
            print(v)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
route = [set() for _ in range(N)]
mark = [None for _ in range(N)]
mark[0] = 0
count = 1

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

while count != N:
    for i in range(N):
        if mark[i] is not None:
            for r in route[i]:
                if mark[r] is None:
                    mark[r] = i
                    count += 1

print("Yes")
[print(m + 1) for m in mark[1:]]

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ans = {i:0 for i in range(1,N+1)}
ans[1] = 10000000
route = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    route[a].append(b)
    route[b].append(a)
z = [1]
x = set(z)
for _ in range(N+1):
    tmp = set()
    for i in x:
        count = 0
        for j in route[i]:
            #print(j)
            if ans[j] == 0:
                ans[j] = i
                count += 1
                tmp.add(j)
    x = tmp
    #print(ans,x)
    if count == 0:
        break
print('Yes')
for i in ans.keys():
    if i != 1:
        print(ans[i])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
li=[[] for i in range(n)]
for i in range(m):
    ai,bi=map(int,input().split())
    li[ai-1].append(bi-1)
    li[bi-1].append(ai-1)
#print(li)
flag=0
fl2=0
for i in range(n):
    if len(li[i])==0:
        flag=1
        break
if flag==1:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        if 0 in li[i]:
            print(1)
        else:
            for j in range(len(li[i])):
                if li[i][j] in li[0]:
                    print(li[i][j]+1)
                    fl2=1
                    break
            if fl2==0:
                print(min(li[i])+1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
connections = [list(map(int, input().split())) for _ in range(m)]
weights = [2e5 + 10] * n
weights[0] = 1
directions = [1] * n
for con in connections:
    if con[0] > con[1]:
        tmp = con[0]
        con[0] = con[1]
        con[1] = tmp
connections.sort()
for con in connections:
    r1 = con[0]
    r2 = con[1]
    w1 = weights[r1 - 1]
    w2 = weights[r2 - 1]
    if w1 < 2e5 + 10 and w1 + 1 < w2:
        weights[r2 - 1] = w1 + 1
        directions[r2 - 1] = r1
    if w2 < 2e5 + 10 and w2 + 1 < w1:
        weights[r1 - 1] = w2 + 1
        directions[r1 - 1] = r2

if max(weights) > 2e5 + 5:
    print("No")
else:
    print("Yes")
    for d in directions[1:]:
        print(d)

Submission status: Wrong Answer

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

root = {}
for i in range(M):
  A, B = list(map(int, input().strip().split()))
  if A not in root:
    root[A] = set()
  root[A].add(B)  
  if B not in root:
    root[B] = set()
  root[B].add(A)
    
#print(root)

if 1 not in root or len(root) != N:
  print('No')
else:
  A = {}
  A[1] = 0
  current = 1
  last = 0
  while True:
    #print(f'{current=}')
    #print(A)
    for r in root[current]:
      if r not in A:
        A[r] = current
        last = r
    current = last
    if len(A) == N:
      break

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

Submission status: Wrong Answer

Solution code:
inf = 10**5+1
n,m = map(int,input().split())
p = [inf]*n
for _ in range(m):
  a,b = map(int,input().split())
  A = max(a,b)
  B = min(a,b)
  if p[A-1] > B:
    p[A-1] = B
  if p[B-1] > A:
    p[B-1] = A
p[0] = 'Yes'
if max(p[1:]) == 10**5+1:
  print('No')
else:
  for i in range(len(p)):
    print(p[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
edge=[]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    s=max(a,b)
    t=min(a,b)
    edge.append((t,s))
#unionfind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n


    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]


    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)


        if x == y:
            return


        if self.parents[x] > self.parents[y]:
            x, y = y, x


        self.parents[x] += self.parents[y]
        self.parents[y] = x


    def size(self, x):
        return -self.parents[self.find(x)]


    def same(self, x, y):
        return self.find(x) == self.find(y)
uf = UnionFind(n)
ans=[-1]*n
edges=[[] for _ in range(n)]
for e in edge:
    s, t = e
    if not uf.same(s, t):
        uf.union(s, t)
        edges[s].append(t)
        edges[t].append(s)
#print(edges)
visited=[True]*n
stack=deque([0])
visited[0]=False
while stack:
    x=stack.pop()
    for nx in edges[x]:
        if visited[nx]:
            visited[nx]=False
            stack.append(nx)
            ans[nx]=x
for i in range(1,n):
    if visited[i]:
        print("No")
        exit()
print("Yes")
for i in ans[1:]:
    print(i+1)

Submission status: Wrong Answer

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

road = [[] for _ in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    road[A].append(B)
    road[B].append(A)
# print(road)


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

stack = deque([])
for r in road[1]:
    stack.append(r)


def dfs(s):
    now = s
    cnt = 1
    while len(stack) > 0:
        next_root = stack.popleft()
        # print("now ", now)
        # print("next ", next_root)

        for r in road[now]:
            if ans[r] == -1:
                stack.append(r)
                ans[r] = now

        now = next_root
        # print(ans)
        # print("stack", stack)
        # print()
dfs(1)

temp = set(ans)
if ((-1) in temp):
    print("No")
else:
    print("Yes")
    for a in ans[2:]:
        print(a)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

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

for i in range(n):
    if len(arr[i])==0:
        print('No')
        sys.exit()
print(arr)

def bfs(d):
    que=deque()
    que.append(0)
    ans=[0]*n
    while que:
        x=que.popleft()
        if x==0:
            for i in arr[x]:
                ans[i]=1
                que.append(i)
        else:
            for i in arr[x]:
                if ans[i]==0 and i!=0:
                    ans[i]=x+1
                    que.append(i)
    print('Yes')
    for i in range(1,n):
        print(ans[i])        

bfs(arr)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ai=[]
bi=[]
l=[0]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    ai.append(a)
    bi.append(b)

    if a==1:
        l[b]=1
    elif b==1:
        l[a]=1
cnt=0
fl=[0]
while True:
    cnt+=1
    f=0
    for i in range(m):
        if l[ai[i]]==cnt and l[bi[i]]==0:
            l[bi[i]]=cnt+1
        elif l[bi[i]]==cnt and l[ai[i]]==0:
            l[ai[i]]=cnt+1
        elif l[ai[i]]==l[bi[i]]!=0:
            f+=1
    fl.append(f)
    if fl[-1]==fl[-2]!=0:
        for z in range(2,n+1):
            if l[z]==0:
                print("No")
                exit()
        print("Yes")

        for j in range(2,n+1):
            print(l[j])
        exit()
    cnt+=1

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
#import math
#import itertools
#import re
#from functools import lru_cache

input = sys.stdin.readline
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def main():
    n, m = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for _ in range(m)]
    graph = [set() for _ in range(n)]
    for a, b in AB:
        graph[a-1].add(b)
        graph[b-1].add(a)
    dist = np.ones(n)
    dist *= -1
    dist[0] = 0
    queue = [[1]]
    while True:
        positions = queue.pop()
        for p in positions:
            queue_next = []
            for next in graph[p-1]:
                if dist[next-1] == -1:
                    dist[next-1] = p
                    queue_next.append(next)
        if len(queue_next) == 0:
            break
        queue.append(queue_next)
    if np.count_nonzero(dist == -1) > 0:
        print('No')
    else:
        print('Yes')
        for d in dist[1:]:
            print(int(d))




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = [ int(i) for i in input().strip().split(' ')]

miti = [0] * (N - 1)
path = { i:set() for i in range(1, N+1)}
routes = []
for i in range(M):
    Ai, Bi = [ int(i) for i in input().strip().split(' ')]
    path[Ai].add(Bi)
    path[Bi].add(Ai)

targets = set([1])
check_list = set([1])

while True:
#    print(targets)
    for target in targets:
        targets = []
        for t in path[target]:
            if miti[t-2] == 0:
                miti[t-2] = target
        targets += path[target]
        check_list.add(target)
    targets = set(targets) - check_list
    if len(check_list) == N:
        print('Yes')
        for mt in miti:
            print(mt)
        break
    if len(targets) == 0:
        print('No')
        break

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M=list(map(int,input().split()))
l=[[] for i in range(N)]
l2=np.zeros(N-1)
import sys
l_l=[i.rsplit() for i in sys.stdin.readlines()]
l_l = [list(map(int,i)) for i in l_l]
for i in l_l:
   l[i[0]-1].append(i[1])
   l[i[1]-1].append(i[0])
from collections import deque
que=deque([1])
after=deque()
que_append=que.append
after_append=after.append
while que != deque([]):
   X=que.popleft()
   after_append(X)
   for i in l[X-1]:
      if i in after:
         continue
      if i in que:
         continue
      que_append(i)
      np.put(l2,[i-2],X)
if len(after) == N:
   print("Yes")
   for i in l2:
      print(i)
else:
   print("No")

Submission status: Wrong Answer

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

print('Yes')
for ll in list:
    if ll == list[0]:
        continue
    for j in range(len(ll)):
        if ll[j] == 1:
            print(j+1)
            break

Submission status: Wrong Answer

Solution code:
import math


def main():
    print('No')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = tuple(map(int, input().split()))
paths = [tuple(map(int, input().split())) for _i in range(m)]

shirube = [0] * n

for f, t in paths:
    temp_path = shirube[f - 1] + 1

    if shirube[t - 1] == 0 or temp_path < shirube[t - 1]:
        shirube[t - 1] = temp_path

if all([e != 0 for e in shirube[1:]]):
    print("Yes")
else:
    print("No")

for e in shirube[1:]:
    print(e)

Submission status: Wrong Answer

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

root = []
for i in range(m):
    root.append(list(map(int, input().split())))

#room_li = list(range(1,n+1))

answer_li  = [0]*n

now_li  = [1]

next_now = []

delete_li = []

while True:
    for n in now_li:
        for i, r in enumerate(root):
            if n in r:
                #root.pop(i)
                delete_li.append(i)
                r.remove(n)
                dest = r[0]
                if answer_li[dest-1] == 0:
                    answer_li[dest-1] = n
                next_now.append(dest)
        cnt = 0
        for d in delete_li:
            root.pop(d-cnt)
            cnt += 1
        delete_li = []
    now_li = next_now
    next_now = []

    if len(root) <=1:
        break
answer_li = answer_li[1:]
print(answer_li)
if 0 not in answer_li:
    print('Yes')
    for i in answer_li:
        print(i)
else:
    print('No')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

import networkx as nx

YES = "Yes"  # type: str
NO = "No"


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G = nx.Graph()
    G.add_nodes_from([1+n for n in range(N)])

    G.add_edges_from([(a,b) for a,b in zip(A,B)])

    paths = nx.single_source_shortest_path_length(G, 1)

    print(YES)
    for key, val in paths.items():
        if key != 1:
            print(val)
    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: Wrong Answer

Solution code:
n,m=map(int,input().split())
ne=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  ne[a].append(b)
  ne[b].append(a)
print('Yes')

ans=[0]*(n+1)
check0=[1]
check1=[]
for i in range(m-1):
  for j in check0:
    check1+=ne[j]
    for k in ne[j]:
      if ans[k]==0:
        ans[k]=j
  check1=list(sorted(check1))
  check0=check1.copy()
for i in ans[2:]:
  print(i)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ans = {i:0 for i in range(1,N+1)}
ans[1] = 10000000
route = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    route[a].append(b)
    route[b].append(a)
x = [1]
for _ in range(N+1):
    tmp = []
    for i in x:
        count = 0
        for j in route[i]:
            #print(j)
            if ans[j] == 0:
                ans[j] = i
                count += 1
                tmp.append(j)
    x = tmp
    print(ans,x)
    if count == 0:
        break
print('Yes')
for i in ans.keys():
    if i != 1:
        print(ans[i])

Submission status: Wrong Answer

Solution code:
def check(go):
    for i in range(1, len(go)):
        if (go[i] == -1):
            return True

    return False


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

G = [[0]*N for i in range(N)]
for i in range(M):
    A, B = list(map(int, input().split()))

    G[A-1][B-1] = 1
    G[B-1][A-1] = 1

go = [1]
go.extend([-1] * (N - 1))

flag = [False] * N


go_before = -1
go_after = 0

while(go_before != go_after):
    go_before = go_after
    for i in range(N):
        if (flag[i] == True):
            continue
        else:
            flag[i] = True
            for j in range(N):
                if (go[j] == -1 and G[i][j] == 1):  # 未定 and いけるなら
                    go[j] = i
                    go_after += 1
        if (check(go) == False):
            print("Yes")
            for i in range(1, len(go)):
                print(go[i] + 1)
            exit(0)


print("No")

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict


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

    # distances = [[0 if i == j else inf for j in range(N + 1)] for i in range(N + 1)]
    signs = [-1 for _ in range(N + 1)]
    dists = [N for _ in range(N + 1)]

    path = [(a, b) if a <= b else (b, a) for a, b in A_B]

    for a, b in sorted(A_B):
        if a == 1:
            dists[b] = 1
            signs[b] = 1
        elif b == 1:
            dists[a] = 1
            signs[a] = 1
        else:
            if dists[a] - dists[b] > 1:
                dists[a] = dists[b] + 1
                signs[a] = b
            elif dists[b] - dists[a] > 1:
                dists[b] = dists[a] + 1
                signs[b] = a
            else:
                pass

    # print(dists)
    # print(signs)

    print('Yes')
    for s in signs[2:]:
        print(s)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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",d)
    s={1}
    point=0
    while(n>0):
        t=set([])
        point+=1
        for i in s:
            for j in d[i]:
                if e[j]==0:
                    e[j]=point
                    t|={j}
                    n-=1
        s=t
    for k,v in e.items():
        if k>0:
            print(v)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)
n,m=map(int,input().split())
l=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
#print(l)
def dfs(p,pearent,count):
  min=10**7
  #print(pearent)
  if 0 in l[p]:
    return count+1
  for i in range(len(l[p])):
    if l[p][i]==pearent:continue
    tmp=dfs(l[p][i],p,count+1)
    if min>tmp:
      min=tmp
  return min
ans=[]
for i in range(1,n):
  ans.append(dfs(i,0,0))
if 10**7 in ans:
  print('No')
else:
  print('Yes')
  for i in ans:
    print(i)
#print(dfs(1,0,0))

Submission status: Wrong Answer

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

dic = {i:set() for i in range(1, N+1)}

for _ in range(M):
    a, b = map(int, input().split())
    dic[a].add(b)
    dic[b].add(a)


l1 = [float('inf')]*N
l1[0] = 0
ans = [0] * N

for k1, rooms in dic.items():
    for room in rooms:
        if l1[k1-1] + 1 < l1[room-1]:
            l1[room-1] = l1[k1-1] + 1
            ans[room-1] = k1

if float('inf') in l1:
    print('No')
else:
    print('Yes')
    for n in ans[1:]:
        print(n)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
#import math
#import itertools
#import re
#from functools import lru_cache

input = sys.stdin.readline
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def main():
    n, m = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for _ in range(m)]
    print(AB)
    graph = [set() for _ in range(n)]
    for a, b in AB:
        graph[a-1].add(b)
        graph[b-1].add(a)
    dist = np.ones(n)
    dist *= -1
    dist[0] = 0
    queue = [[1]]
    while True:
        positions = queue.pop()
        for p in positions:
            queue_next = []
            for next in graph[p-1]:
                if dist[next-1] == -1:
                    dist[next-1] = p
                    queue_next.append(next)
        if len(queue_next) == 0:
            break
        queue.append(queue_next)
    if np.count_nonzero(dist == -1) > 0:
        print('No')
    else:
        print('Yes')
        for d in dist[1:]:
            print(int(d))




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

route = deque([ [0] for i in range(n)])

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

mi = deque([10**6] * n)
mi[0] = 0
check = deque([n] * n)

for i in range(len(route)):
    for j in route[i]:
        if mi[j] > mi[i] + 1:
            mi[j] = mi[i] + 1
            check[j] = i

for i in mi:
    if i == 10**6:
        print("No")
        exit()

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

Submission status: Wrong Answer

Solution code:
import sys
# from random import choice,randint
# from bisect import bisect_left as bl             
# from bisect import bisect_right as br  
from collections import deque,defaultdict,Counter
# from math import sqrt,floor,ceil
# from itertools import combinations,permutations
# from heapq import heapify,heappop,heappush,heappushpop
# inp=sys.stdin.readline
# out=sys.stdout.write
# flsh=sys.stdout.flush
# ranomd string generator --> a = ''.join(random.choices(string.ascii_lowercase, k = 1000))
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod1=998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

#fact=[1]
#for i in range(1,100001):
#    fact.append((fact[-1]*i)%mod)
#ifact=[0]*100001
#ifact[100000]=pow(fact[100000],mod-2,mod)
#for i in range(100000,0,-1):
#    ifact[i-1]=(i*ifact[i])%mod
 
def MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()] #use list comprehension for loops
def LF(): return [float(x) for x in inp().strip().split()] #use try and except for dictionaries
def LS(): return inp().strip().split() #declare local variables ... for functions assing them to variables
def I(): return int(inp().strip()) # before using example ... func = len for using len() funtcion
def F(): return float(inp().strip()) #sort dictionary after zipping
def S(): return inp().strip() #use map function for mapping list to a fuction
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a)) #use this for string concatenation
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)
def modinv(n,p):return pow(n,p-2,p)
def ncr(n,r,p):                      
    t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
    return t

####################Actualcode################################
def main():
    n,m=MI()
    d = defaultdict(list)
    for i in range(m):
        a,b=MI()
        d[a].append(b)
        d[b].append(a)
    ans = [0]*(n+1)
    for i in d[1]:
        ans[i]=1
        for j in d[i]:
            if ans[j]==0:
                ans[j]=i
    for i in d:
        if ans[i]==0:
            for j in d[i]:
                if ans[j]!=0:
                    ans[i]=j
                    break
    flag = 0
    for i in range(2,len(ans)):
        if ans[j]==0:
            flag=1
            break
    if flag==1:
        print("No")
    else:
        print("Yes")
        for i in range(2,len(ans)):
            print(ans[i])

######## Python 2 and 3 footer by Pajenegod and c1729
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

inp = lambda: sys.stdin.readline().rstrip('\r\n')
out = lambda x: sys.stdout.write(x)
flsh= lambda: sys.stdout.flush()

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque,defaultdict

N, M = [int(x) for x in stdin.readline().rstrip().split()]

par = [i for i in range(N+1)]
rank = [0] * (N+1)
size = [1] * (N+1)


def find(x):
    if par[x] == x:
        return par[x]
    else:
        par[x] = find(par[x])
        return par[x]


def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
        size[y] += size[x]
        size[x] = 0

    else:
        par[y] = x
        size[x] += size[y]
        size[y] = 0
        if rank[x] == rank[y]:
            rank[x] += 1


def check_same(x, y):
    return find(x) == find(y)


def check_size(x):
    return size[find(x)]



from collections import defaultdict
adj = defaultdict(set)

for _ in range(M):
    A, B = [int(x) for x in stdin.readline().rstrip().split()]
    union(A, B)
    adj[A].add(B)
    adj[B].add(A)
 
print("Yes")
ans = [0]*(N+1)
visit_p = deque()
visit_p.append((1,0))
visited = [False]*(N+1)
visited[1] = True
dist = [10**18]*(N+1)

while visit_p:
  now_v,distance = visit_p.popleft()
  for v in adj[now_v]:
    if visited[v]:
      continue

      if distance < dist[v]:
        ans[v] = now_v
        dist[v] = min(dist[v],distance)


        visited[v] = True
        visit_p.append((v,1+distance))

        for k in ans[2:]:
          print(k)

Submission status: Wrong Answer

Solution code:
# N, M = 6, 9
# ARR = [
#     [3, 4],
#     [6, 1],
#     [2, 4],
#     [5, 3],
#     [4, 6],
#     [1, 5],
#     [6, 2],
#     [4, 5],
#     [5, 6],
# ]
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
ARR = []

for i in range(M):
    ARR.append(list(map(int, input().split())))


def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStates = [False for i in range(n)]
    nodeResults = [0 for i in range(n - 1)]
    for i in range(m):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1

        nodes[startNode].append(endNode)
        nodes[endNode].append(startNode)

    return nodes, nodeStates, nodeResults


nodes, nodeStates, nodeResults = prepare(N, M, ARR)


def dfs(currentNode, parentNode, nodes):
    childrenNodes = nodes[currentNode]

    if nodeStates[currentNode] > 0:
        return

    if currentNode >= 1:
        nodeResults[currentNode - 1] = parentNode + 1

    nodeStates[currentNode] = True
    for childNode in childrenNodes:
        dfs(childNode, currentNode, nodes)


dfs(0, -1, nodes)

if sum(nodeStates) == N:
    print("Yes")
    for i in range(N - 1):
        print(nodeResults[i])
else:
    print("No")