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:
import sys
from collections import deque
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M = map(int, input().split())
 
G = [[] for _ in range(N + 1)]
m = map(int, read().split())
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)
 
par = [0] * (N + 1)
visited = [0] * (N + 1)
root = 1
visited[root] = 1
q = deque([root])
while q:
    v = q.popleft()
    for w in G[v]:
        if visited[w]:
            continue
        visited[w] = 1
        par[w] = v
        q.append(w)
 
print('Yes')
print(*par[2:], sep='\n')

Submission status: Wrong Answer

Solution code:
INF=99999
N,M=map(int,input().split())
#隣接リスト
tolist=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    tolist[a-1].append(b-1)
    tolist[b-1].append(a-1)
#始点から幅優先探索
pathlist=[0]
roomsign=[INF]*N
roomsign[0]=1
#空になるまで実行 先頭を削除して取得
while pathlist:
    nth=pathlist.pop(0)
    for i in tolist[nth]:
        if roomsign[i]==INF:
            roomsign[i]=nth+1
            pathlist.append(i)

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

Submission status: Wrong Answer

Solution code:
INF=99999
N,M=map(int,input().split())
#隣接リスト
tolist=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    tolist[a-1].append(b-1)
    tolist[b-1].append(a-1)
#始点から幅優先探索
pathlist=[0]
roomsign=[INF]*N
roomsign[0]=1
#空になるまで実行 先頭を削除して取得
while pathlist:
    nth=pathlist.pop(0)
    for i in tolist[nth]:
        if roomsign[i]==INF:
            roomsign[i]=nth+1
            pathlist.append(i)

print("Yes")
print(*roomsign[1:N],sep="\n")

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = [int(e) for e in input().split()]
AB = [[] for _ in range(n+1)]
for i in range(m):
    A,B = [int(e) for e in input().split()]
    AB[A].append(B)
    AB[B].append(A)

ans = [0]*(n+1)
visited = [0]*(n+1)
root = 1
visited[root] = 1
q = deque([root])

while q:
    v = q.popleft()
    for w in AB[v]:
        if visited[w]==0:
            ans[w]=v
            visited[w] +=1
            q.append(w)
        
print('YES')
for i in ans[2:]:
    print(i)

Submission status: Wrong Answer

Solution code:

from sys import stdin
from collections import deque


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ipt = [[int(y) for y in x.rstrip().split()] for x in stdin.readlines()]
    MOD = 100100100100100100

    pl = [0] * (N + 1)

    for a, b in ipt:
        if pl[a] == 0:
            pl[a] = [b]
        else:
            pl[a].append(b)
        if pl[b] == 0:
            pl[b] = [a]
        else:
            pl[b].append(a)

    print(pl)

    que = deque([1])
    deep = [MOD] * (N + 1)
    deep[1] = 0
    deep[0] = 0
    arrow = [0] * (N + 1)
    cnt = 1

    while not not que:
        q = que.popleft()
        tmp = False
        for i in pl[q]:
            if deep[i] != MOD:
                continue
            deep[i] = deep[q] + 1
            arrow[i] = q
            tmp = True
            cnt += 1
        if tmp:
            que.extend(pl[q])

    if N != cnt:
        print("No")
    else:
        print("Yes")
        for i in arrow[2:]:
            print(i)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(start, line):
    quene = deque([start])
    d = [None] * len(line) # reset distance from start
    d[start] = 0
    while quene:
        v = quene.popleft()
        for i in line[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                quene.append(i)
    return d


def main():
    n,w = map(int,input().split()) #n:頂点数　w:辺の数
    checker = [0]
    line = [[] for _ in range(n)]
    for i in range(w):
        x,y= map(int,input().split()) 
        x -= 1
        y -= 1
        line[x].append(y)
        line[y].append(x)
    print("Yes")
    ans = bfs(0,line)
    for i in ans[1:]:
        print(i)

 
 
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
graph = [set() for _ in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    graph[ai-1].add(bi-1)
    graph[bi-1].add(ai-1)

signposts = [-1] * (n-1)


def bfs(start, graph, signposts):
    stack = [start]
    while (stack):
        visiting = stack.pop(0)
        for i in graph[visiting]:
            if signposts[i-1] == -1:
                stack.append(i)
                signposts[i-1] = visiting


bfs(0, graph, signposts)

if -1 in signposts:
    print("No")
else:
    print("Yes")
    for i in range(n-1):
        print(signposts[i]+1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
graph = [set() for _ in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    graph[ai-1].add(bi-1)
    graph[bi-1].add(ai-1)

signposts = [-1] * (n-1)


def bfs(start, graph, signposts):
    stack = [start]
    while (stack):
        visiting = stack.pop(0)
        for i in graph[visiting]:
            if signposts[i-1] == -1:
                stack.append(i)
                signposts[i-1] = visiting


bfs(0, graph, signposts)

if - 1 in signposts:
    print("No")
else:
    print("Yes")
    for i in range(n-1):
        print(signposts[i]+1)

Submission status: Wrong Answer

Solution code:
import sys

max_int = 1000000001  # 10^9+1
min_int = -max_int

n, m = map(int, sys.stdin.readline().split())
G = {}
for _m in range(m):
    a, b = map(int, sys.stdin.readline().split())
    if a not in G:
        G[a] = [[b], -1]
    else:
        G[a][0].append(b)

    if b not in G:
        G[b] = [[a], -1]
    else:
        G[b][0].append(a)

pretends = [1]
L = -1
while pretends:
    L += 1
    new_pretends = []
    for pretend in pretends:
        if G[pretend][1] != -1:
            continue
        G[pretend][1] = L
        for neighbor in G[pretend][0]:
            new_pretends.append(neighbor)
    pretends = new_pretends

for vertex in G:
    if G[vertex][1] == -1:
        print('NO')
        exit()

print('YES')

for i in range(2, n + 1):
    for neighbor in G[i][0]:
        if G[neighbor][1] == G[i][1] - 1:
            print(neighbor)
            break

Submission status: Wrong Answer

Solution code:
import heapq

# def heapify(x):
#     for i in range((x)):
#         x[i] = -x[i]
#     heapq.heapify(x)

# def heappush(heap, item):
#     heapq.heappush(heap, -item)

# def heappop(heap):
#     return -heapq.heappop(heap)

# from heapq import heappop, heappush
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


def raw_input():
    return input()


rooms_count, passages_count = map(int, raw_input().split())
adj = []
for i in range(0, rooms_count):
    adj.append([])

for j in range(0, passages_count):
    a, b = map(int, raw_input().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)

seen = set()
distance = [10000] * rooms_count
next = [10000] * rooms_count
h = []
heapq.heappush(h, (0, 0, -1))
while len(h):
    (d, room, parent) = heapq.heappop(h)
    if (distance[room] <= d):
        continue
    distance[room] = d
    next[room] = parent
    seen.add(room)

    for neighbor in adj[room]:
        heapq.heappush(h, (d + 1, neighbor, room))

if len(seen) == rooms_count:
    print('Yes')
    for room in range(1, rooms_count):
        print(next[room] + 1)
else:
    print('No')

Submission status: Wrong Answer

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

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

q = [1]
visit = [1]  + [0] * (n-1)
prev = [0]*n
while q:
    now = q.pop()
    for i in next_node[now-1]:
        if visit[i-1] == 0:
            q.append(i)
            visit[i-1] = 1
            prev[i-1] = now
print('Yes')
print(*prev[1:], sep='\n')

Submission status: Wrong Answer

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

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

q = [1]
visit = [1]  + [0] * (n-1)
prev = [0]*n
while q:
    now = q.pop()
    for i in next_node[now-1]:
        if visit[i-1] == 0:
            q.append(i)
            visit[i-1] = 1
            prev[i-1] = now
print('Yes')
print(prev[1:])

Submission status: Wrong Answer

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

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

q = [1]
visit = [1]  + [0] * (n-1)
prev = [0]*n
while q:
    now = q.pop()
    for i in next_node[now-1]:
        if visit[i-1] == 0:
            q.append(i)
            visit[i-1] = 1
            prev[i-1] = now
print(prev[1:])

Submission status: Wrong Answer

Solution code:
from collections import deque

# 頂点数と辺数
N, M = map(int, input().split())
# 辺
AB = [map(int, input().split()) for _ in range(M)]

# 無向グラフの隣接リスト設定
link = [[] for _ in range(N + 1)]
for a, b in AB:
  link[a].append(b)
  link[b].append(a)

# BFSのデータフレーム
dist = [-1] * (N + 1)  # 看板未設定
que = deque([1])       # 頂点1を始点とした訪問キュー

# BFS 開始 (キューが空になるまで探索を行う)
while que:
    v = que.popleft() # キューから先頭頂点(現在地)v取得

    for i in link[v]:
      # 未設定頂点iに現在地への看板を設定し訪問キューに追加する
      if dist[i] == -1:
        dist[i] = v
        que.append(i)

# 結果出力（各頂点に設置する看板）
print(dist)        
print('Yes')
print('\n'.join(str(v) for v in dist[2:]))

Submission status: Wrong Answer

Solution code:
#この解答を自分で写経してみる
N,M=map(int,input().split())
AB=[map(int,input().split()) for _ in range(M)]
#map関数を格納したリストを作る
#この_表記で繰り返すという文化に慣れよう

links=[[] for _ in range(N+1)]
#移動先を出力する
#リストの入れ子にしたかったら、最初から入れ子として定義しないといけない
#何か + for _ in range(M)　で、何かをM回繰り返す
for a,b in AB:
#map関数それぞれに対して、値を抽出する
    links[a].append(b)
    links[b].append(a)

from collections import deque
result=[-1]*(N+1)
#これで[-1,-1,,,]のリストは作れる
#各部屋ごとの出力先

q=deque([1])
#始点の定義
while len(q)>0:
    i=q.popleft()
    for j in links[i]:
        if result[j] ==-1:
            result[j] = i
            #新しいものをどんどん加えていくことで、層がどんどん深くなっていく
            q.append(j)
print("yes")
print("\n".join(str(i) for i in result[2:] ))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
L = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    A = a - 1
    B = b - 1
    L[A].append(B)
    L[B].append(A)
# print(L)
BFS = list()
BFS.append([0])
ans = [[] for i in range(n - 1)]
while [] in ans:
    s = set()
    S = set()
    for i in BFS[-1]:
        if not(i in S):
            for j in L[i]:
                ans[j-1].append(i+1)
        s = s | set(L[i])
    s = s - S
    S = S | s
    BFS.append(s)
print('Yes')
for i in range(n - 1):
    print(ans[i][0])

Submission status: Wrong Answer

Solution code:
#この解答を自分で写経してみる
N,M=map(int,input().split())
AB=[map(int,input().split()) for _ in range(M)]
#map関数を格納したリストを作る
#この_表記で繰り返すという文化に慣れよう

links=[[] for _ in range(N+1)]
#移動先を出力する
#リストの入れ子にしたかったら、最初から入れ子として定義しないといけない
#何か + for _ in range(M)　で、何かをM回繰り返す
for a,b in AB:
#map関数それぞれに対して、値を抽出する
    links[a].append(b)
    links[b].append(a)

from collections import deque
result=[-1]*(N+1)
#これで[-1,-1,,,]のリストは作れる
#各部屋ごとの出力先

q=deque([1])
#始点の定義
while len(q)>0:
    i=q.popleft()
    for j in links[i]:
        if result[j] ==-1:
            result[j] = i
            #新しいものをどんどん加えていくことで、層がどんどん深くなっていく
            q.append(j)
    print("yes")
    print("\n".join(str(i) for i in result[2:] ))

Submission status: Wrong Answer

Solution code:

from collections import deque

room_num, path_num = map(int, input().split(" "))
graph = [[] for _ in range(room_num)]
dis = [-1] * room_num
for _ in range(path_num):
    a, b = map(int, input().split(" "))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
dis[0] = 0
q = deque()
q.append(0)
while q:
    pop = q.popleft()
    for n in graph[pop]:
        if dis[n] > 0:
            pass
        else:
            dis[n] = pop+1
            q.append(n)
dis.append(-1)
if -1 in dis:
    print("No")
else:
    del dis[0]
    print("Yes")
    for s in dis:
        print(s)

Submission status: Wrong Answer

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

data=[list(map(int,input().split())) for i in range(M)]
data2=[[1,0]]


def check(i):
    for d2 in data2:
        if d2[0]==i:
            return True
    return False

def get(i):
    for d2 in data2:
        if i==d2[0]:
            return d2[1]
def research(i):
    #print('research',i)
    temp=[]
    for d in data:
        bef=0
        aft=0
        if i==d[0]:
            bef,aft=d[0],d[1]
        elif i==d[1]:
            bef,aft=d[1],d[0]
        else:
            continue
        #print('bef.aft',bef,aft)
        if check(aft):
            continue

        data2.append([aft,get(i)+1])
        temp.append(aft)
    for aft in temp:
        research(aft)

research(1)
#print(data2)

print('Yes')

for i in range(N+1):
    i=N-i
    for d2 in data2:
        if i==d2[1]:
            print(d2[0])
            break

Submission status: Wrong Answer

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

data=[list(map(int,input().split())) for i in range(M)]
data2=[[1,0]]


def check(i):
    for d2 in data2:
        if d2[0]==i:
            return True
    return False

def get(i):
    for d2 in data2:
        if i==d2[0]:
            return d2[1]
def research(i):
    #print('research',i)
    temp=[]
    for d in data:
        bef=0
        aft=0
        if i==d[0]:
            bef,aft=d[0],d[1]
        elif i==d[1]:
            bef,aft=d[1],d[0]
        else:
            continue
        #print('bef.aft',bef,aft)
        if check(aft):
            continue

        data2.append([aft,get(i)+1])
        temp.append(aft)
    for aft in temp:
        research(aft)

research(1)
#print(data2)

print('Yes')
for i in range(2,N+1,1):
    for d2 in data2:
        if i==d2[0]:
            #print(d2)
            cost=d2[1]
            for d2 in data2:
                #print('cost',cost)
                if d2[1]==cost-1:
                    print(d2[0])
                    continue

Submission status: Wrong Answer

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

data=[list(map(int,input().split())) for i in range(M)]
data2=[[1,0]]


def check(i):
    for d2 in data2:
        if d2[0]==i:
            return True
    return False

def get(i):
    for d2 in data2:
        if i==d2[0]:
            return d2[1]
def research(i):
    #print('research',i)
    temp=[]
    for d in data:
        bef=0
        aft=0
        if i==d[0]:
            bef,aft=d[0],d[1]
        elif i==d[1]:
            bef,aft=d[1],d[0]
        else:
            continue
        #print('bef.aft',bef,aft)
        if check(aft):
            continue

        data2.append([aft,get(i)+1])
        temp.append(aft)
    for aft in temp:
        research(aft)

research(1)
#print(data2)

for i in range(2,N+1,1):
    for d2 in data2:
        if i==d2[0]:
            #print(d2)
            cost=d2[1]
            for d2 in data2:
                #print('cost',cost)
                if d2[1]==cost-1:
                    print(d2[0])
                    continue

Submission status: Wrong Answer

Solution code:
import queue

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

que = queue.Queue()
dist = [float('inf')]*n
pre = [-1]*n

dist[0] = 0
que.put(0)
while not que.empty():
  v = que.get()
  for u in to[v]:
    if dist[u]!=float('inf'):
      continue
    dist[u] = dist[v] + 1
    pre[u] = v
    que.put(u)

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

Submission status: Wrong Answer

Solution code:
import networkx as nx
N,M = map(int, input().split())
E = [list(map(int, input().split())) for i in range(M)]

G = nx.Graph() 
G.add_edges_from(E)
di = nx.predecessor(G, source = 1)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int,input().split())
def vertex_count()  -> list:
    v_c = [[] for _ in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        v_c[a].append(b)
        v_c[b].append(a)
    return v_c

def bfs(l) -> list:
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 0
    d = deque()
    d.append(1)
    while d:
        v = d.popleft()
        for i in l[v]:
                if dist[i] != -1:
                    continue
                dist[i] = dist[v] + 1
                d.append(i)
    return dist
if __name__ == "__main__":
    i = vertex_count()
    ans = bfs(i)[3:]
    print("Yes")
    for i in ans:
        print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int,input().split())
def vertex_count()  -> list:
    v_c = [[] for _ in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        v_c[a].append(b)
        v_c[b].append(a)
    return v_c

def bfs(l) -> list:
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 0
    d = deque()
    d.append(1)
    while d:
        v = d.popleft()
        for i in l[v]:
                if dist[i] != -1:
                    continue
                dist[i] = dist[v] + 1
                d.append(i)
    return dist
if __name__ == "__main__":
    i = vertex_count()
    ans = bfs(i)[2:]
    print("Yes")
    for i in ans:
        print(i)

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in input().split()] # nは頂点の数、mは辺の数
g = [[] for _ in range(n+1)] # 隣接リスト

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


from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * (n+1) # uからの距離の初期化
    d[u] = 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)
    return d

# 0からの各頂点の距離
d = bfs(1)
print ('Yes')
ans = '\n'.join(list(map(str, d[2:])))
print (ans)
#print(d)

Submission status: Wrong Answer

Solution code:
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)
 
dist=[-1]*(N+1)
dist[0]=0
dist[1]=0
print(dist)
D=deque()
D.append(1)
 
while D:
    V=D.popleft()
    for i in graph[V]:
        print(i)
        if dist[i]!=-1:
            continue
        dist[i]=V
        D.append(i)
    print("a")
print('Yes')
for j in dist[2:]:
    print(j)

Submission status: Wrong Answer

Solution code:
import itertools
import sys
n,m = map(int,input().split())
a = []
dis = []
for i in range(n):
    dis.append([i + 1,-1] )
for i in range(m):
    a.append(list(map(int, input().split())))

dis[0][1] = 0
tmp = [1]
tmpcnt = 1
dist = 1
b = len(a)
while(tmpcnt != n):
    i = 0
    while(b != i):
        if(a[i][0] == tmp[0]): 
            if(dis[a[i][1] - 1][1] == -1):
                dis[a[i][1] - 1][1] = dist
                tmp.append(a[i][1])
                tmpcnt += 1
            a.remove(a[i])
            b -= 1
            i -= 1   
        elif(a[i][1] == tmp[0]):
            if(dis[a[i][0] - 1][1] == -1):
                dis[a[i][0] - 1][1] = dist
                tmp.append(a[i][0])
                
                tmpcnt += 1
            a.remove(a[i])
            b -= 1
            i -= 1
        i += 1
    tmp.remove(tmp[0])
    if(tmp == []):
        print("No")
        sys.exit();
    dist = dis[tmp[0] - 1][1] + 1

print("Yes")
for i in range(n-1):
    print(dis[i+1][1])

Submission status: Wrong Answer

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

import collections

seen = [-1]*(n+1)
todo = collections.deque()

for i in info[1]:
    todo.append(i)
    seen[i] = 1

while len(todo) != 0:
    now = todo.pop()
    for i in info[now]:
        if seen[i] == -1:
            todo.append(i)
            seen[i] = now

seen = seen[2:]
if -1 in seen:
    print("No")
else:
    print("Yes")
    for i in seen:
        print(i)

Submission status: Wrong Answer

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

import collections

seen = [-1]*(n+1)
todo = collections.deque()

for i in info[1]:
    todo.appendleft(i)
    seen[i] = 1

while len(todo) != 0:
    now = todo.popleft()
    for i in info[now]:
        if seen[i] == -1:
            todo.appendleft(i)
            seen[i] = now

seen = seen[2:]
if -1 in seen:
    print("No")
else:
    print("Yes")
    for i in seen:
        print(i)

Submission status: Wrong Answer

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

import collections

seen = [-1]*(n+1)
todo = collections.deque()

for i in info[1]:
    todo.appendleft(i)
    seen[i] = 1

while len(todo) != 0:
    now = todo.popleft()
    for i in info[now]:
        if seen[i] == -1:
            todo.appendleft(i)
            seen[i] = now

if -1 in seen[1:]:
    print("No")
else:
    seen[0] = "Yes"
    for i in seen:
        print(i)

Submission status: Wrong Answer

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)

# 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
                queue.append(i)
    return d

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

Submission status: Wrong Answer

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)

# 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
                queue.append(i)
    return d

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

Submission status: Wrong Answer

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)
del parent[1]
print(*parent.values())

Submission status: Wrong Answer

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(room)
    # print(plan)
    visited[1][0] = True
    while plan:
        nextque = plan.popleft()
        # print(nextque)
        for i in nextque:
            if visited[i][0] == True:
                # print('true')
                continue
            else:
                # for r in PATH[next]:
                #     plan.append(r)
                plan.append(PATH[i])
                # print(plan)
                visited[i][0] = True
                visited[i][1] = now
        now = i

if __name__ == '__main__':
    PATH = [[] 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: Wrong Answer

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())
    print(a, b)
    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: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[""]*(N+1);a=0;b=0;e="Yes"
S=[0]*(N+1);T=[];U=[0]*(N+1)
for i in range(M):
  a,b=map(str,input().split())
  A[int(a)]=A[int(a)]+b
  A[int(b)]=A[int(b)]+a
#print(A)

for i in range(1,N+1):
  for j in range(len(A[i])):
    T.append(A[i][j])
  S[i]=T
  T=[]
print(S)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int,input().split())
def vertex_node()  -> list:
    v_c = [[] for _ in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        v_c[a].append(b)
        v_c[b].append(a)
    return v_c

def bfs(l) -> list:
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 0
    d = deque()
    d.append(1)
    while d:
        v = d.popleft()
        for i in l[v]:
                if dist[i] != -1:
                    continue
                dist[i] = dist[v] + 1
                d.append(i)
    return dist
if __name__ == "__main__":
    i = vertex_node()
    ans = bfs(i)[2:]
    print("Yes")
    for i in ans:
        print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int,input().split())
def vertex_node()  -> list:
    v_c = [[] for _ in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        v_c[a].append(b)
        v_c[b].append(a)
    return v_c

def bfs(l) -> list:
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 0
    d = deque()
    d.append(1)
    while d:
        v = d.popleft()
        for i in l[v]:
                if dist[i] != -1:
                    continue
                dist[i] = dist[v] + 1
                d.append(i)
    return dist
if __name__ == "__main__":
    i = vertex_node()
    ans = bfs(i)[2:]
    print(*ans)