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: Runtime Error

Solution code:
import sys
from collections import deque


N, M = [int(i) for i in input().split()]
A = []
B = []
for i in range(M):
    l = [int(i) for i in input().split()]
    A.append(l[0])
    B.append(l[1])

# BFS
G = [[] for _ in range(N)]
for i in range(N):
    G[A[i] - 1].append(B[i] - 1)
    G[B[i] - 1].append(A[i] - 1)
G = [list(set(x)) for x in G]

q = deque([])
dist = [-1] * N
ans = [-1] * N
ans[0] = 0
dist[0] = 0
q.appendleft(0)
while(len(q) > 0):
    v = q.pop()
    for nv in G[v]:
        if not dist[nv] == -1:
            continue
        dist[nv] = dist[v] + 1
        ans[nv] = v
        q.appendleft(nv)

for i in ans[1:]:
    if i == -1:
        print('No')
        sys.exit()

for i, v in enumerate(ans):
    if i == 0:
        print('Yes')
        continue
    print(v + 1)

Submission status: Runtime Error

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

for i in range(m):
    ta, tb = map(int, input().split())
    dir[ta].append(tb)
    dir[tb].append(ta)

ans = [0]*(n+1)
flag = [False]*(n+1)
flag[1] = True
que = [1]
while len(que) != 0:
    #print('que: ', len(que), que)
    now = que.pop()
    for to in dir[now]:
        if flag[to]:
            continue
        que.append(to)
        flag[to] = True
        ans[to] = now
"""         print(to)
        ans[to] = now
        flag[to] = 1
        for toto in dir[to]:
            if flag[toto] != 1:
                que.append(toto) """
print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
g = {}
for i in range(M):
  a, b = map(int, input().split())
  if a in g.keys():
    g[a].append(b)
  else:
    g[a] = [b]
  if b in g.keys():
    g[b].append(a)
  else:
    g[b] = [a]
ans = [0 for _ in range(N+1)]
#print(g)
current = [1]
while 0 in ans[2:]:
  #print(ans)
  for i in current:
    next = []
    #print('i',i)
    for j in g[current]:
      if ans[j] == 0:
        ans[j] = i
        next.append(j)
  current = next
print('Yes')
for i in range(2,N+1):
  print(ans[i])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
PATHS = list([tuple(map(lambda t: int(t) - 1, input().split())) for i in range(M)])

depths = [None] * N
guides = [None] * N

def func(cuurent, depth):
    depths[cuurent] = depth

    ls = []

    for r1, r2 in PATHS:
        if r1 == cuurent and (depths[r2] == None or depths[r2] > depth + 1):
            depths[r2] = depth + 1
            guides[r2] = cuurent
            ls.append(r2)
        
        if r2 == cuurent and (depths[r1] == None or depths[r1] > depth + 1):
            depths[r1] = depth + 1
            guides[r1] = cuurent
            ls.append(r1)
    
    for room in ls:
        func(room, depth + 1)

func(0, 0)
#print(depths)
#print(guides)

#if not all([follow_guide(i, guides) == depths[i] for i in range(1, N)]):
if False:
    print("No")

else:
    print("Yes")

    for i in guides[1:]:#
        print(i + 1)

Submission status: Runtime Error

Solution code:
f=lambda:map(int,input().split())
n,m=f()
g = [[] for _ in range(m)]
for _ in range(m):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
p = [0]*n
from collections import deque
q = deque([0])

while q:
  v = q.popleft()
  for c in g[v]:
    if p[c]<1:p[c]=v+1;q.append(c)
if 0 in p: print('No')
else: print('Yes',*p[1:],sep='\n')

Submission status: Runtime Error

Solution code:

n, m = map(int, input().split())
table = [[] for i in range(n+1)]
ans = [(1e9, 0) for i in range(n+1)]
def func(node, num, li):
    for i in li:
        if num < ans[i][0]:
            ans[i] = (num, node)
            func(i, num+1, table[i])
        # print(ans[2:])


# print(table)
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)

# print(table)


num = 1



func(1, num, table[1])
# print(ans[2:])
ans_ = []
for i in ans[2:]:
    ans_.append(i[1])
# print(ans_)
if 1e9 in ans_:
    print("No")
else:
    print("Yes")
    for i in ans_:
        print(i)


# print(table)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g = [[] for _ in range(m)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
p = [0]*n
from collections import deque
q = deque([0])

while q:
  v = q.popleft()
  for c in g[v]:
    if p[c]<1:p[c]=v+1;q.append(c)
if 0 in p: print('No')
else: print('Yes',*p[1:],sep='\n')

Submission status: Runtime Error

Solution code:
import collections

if __name__ == '__main__':
    n, m = map(int, input().split())
    l = [list(map(int, input().split())) for i in range(m)]

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

    for i in l:
        ways[i[0]].append(i[1])
        ways[i[1]].append(i[0])

    #print(ways)

    q = collections.deque()

    ans = [-1] * n # 道案内
    ans[0] = 0

    q.append(1)

    while(len(q) != 0):
        item = q.popleft()
        for i in ways[item]:
            if ans[i-1] == -1:
                ans[i-1] = item
                q.append(i)
                #print(ans , i , item)

    if -1 in ans:
        print("No")

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
L=[set() for i in range(n)]
for i in range(m):
    a, b =  map(int, input().split())
    L[a-1] |= {b}
    L[b-1] |= {a}
Y = {range(1, n+1)}
Z = [0]*(n-1) 
S = {1}
def f(X):
    global S, Z
    X_next = set()
    for j in X:
        R = L[j-1]-S
        S |= L[j-1]
        X_next |= R
        for k in R:
            Z[k-2] += j
    if X_next == set():
        print("Yes")
        print('\n'.join(map(str, Z)))
    else:
        return  f(X_next)
f({1})

Submission status: Runtime Error

Solution code:
from collections import deque
def main():
  n,m=map(int,input().split())
  e=[[]for _ in range(n)]
  for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    e[a].appned(b)
    e[b].append(a)
  ans=[-1]*n
  ans[0]="Yes"
  dq=deque([0])
  while dq:
    g=dq.popleft()
    for v in e[g]:
      if ans[v]==-1:
        ans[v]=g+1
        dq.append(v)
  print(*ans)
main()

Submission status: Runtime Error

Solution code:
u

Submission status: Runtime Error

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

for i in range(m):
    ta, tb = map(int, input().split())
    dir[ta].append(tb)
    dir[tb].append(ta)

ans = [0]*(n+1)
flag = [0]*(n+1)
flag[1] = 1
que = [1]
while len(que) != 0:
    print('que: ', len(que), que)
    now = que.pop()
    for to in dir[now]:
        if flag[to] == 1:
            continue
        que.append(to)
        flag[to] = 1
        ans[to] = now
"""         print(to)
        ans[to] = now
        flag[to] = 1
        for toto in dir[to]:
            if flag[toto] != 1:
                que.append(toto) """
print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g = [[] for _ in range(m)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
p = [0]*n
from collections import deque
q = deque([0])

while q:
  v = q.popleft()
  for i in g[v]:
    if p[i]<1:p[i]=v+1;q.append(i)
if 0 in p: print('No')
else: print('Yes',*p[1:],sep='\n')

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
L=[set() for i in range(n)]
for i in range(m):
    a, b =  map(int, input().split())
    L[a-1] |= {b}
    L[b-1] |= {a}
# L=[{2,3}, {4,5}, {1,4}, ...]
# 1→{2,3}→{4,5}
Y = {range(1, n+1)}
Z = [0]*(n-1) 
S = {1}
def f(X):
    global S, Z
    X_next = set()
    for j in X:
        R = L[j-1]-S
        S |= L[j-1]
        X_next |= R
        for k in R:
            Z[k-2] += j
    if X_next == set():
        print("Yes")
        print('\n'.join(map(str, Z)))
    else:
        return  f(X_next)
f({1})

Submission status: Runtime Error

Solution code:

flags = {}
edges = {}

def dfs(next, before, distance):
    global flags, edges
    if next == 1:
        return
    elif flags[next][1] < distance:
        return
    else:
        flags[next][0] = before
        flags[next][1] = distance
        nexts_tmp = edges[next]
        for n in nexts_tmp:
            dfs(n, next, distance + 1)

def main():
    global flags, edges
    n, m = map(int, input().split())
    flags = {e:[0, n+1] for e in range(1, n + 1)}
    edges = {e:set() for e in range(1, n + 1)}
    for _ in range(m):
        a, b = map(int, input().split())
        edges[a].add(b)
        edges[b].add(a)

    next_from1 = edges[1]
    for n1 in next_from1:
        dfs(n1,1,1)
    result = [flags[f][1] < (n + 1) for f in flags if f > 1]
    if not all(result):
        print('No')
    else:
        print('Yes')
        for i1 in range(2, n + 1):
            print(flags[i1][0])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# list(map(int, input().split()))
# int(input())
from collections import deque

def main(AB, N, M):

    def serch(st = {1}, already = {1}, dict = {1:1}):
        next_dict = dict.copy()
        # for l in st:
        #     for i in [ab[0] if ab[1] == l else ab[1] for ab in AB if l in ab]:
        #         next_dict.setdefault(i, l)

        # next_dict.update({i:l for l in st for i in [ab[0] if ab[1] == l else ab[1] for ab in AB if l in ab]})

        # [next_dict.setdefault(i, l) for l in st for i in [ab[0] if ab[1] == l else ab[1] for ab in AB if l in ab]]
        # next_st = {k for k in next_dict if k not in already}

        # next_dict.update({i:l for l in st for i in [ab[0] if ab[1] == l else ab[1] for ab in AB if l in ab] if i not in already})

        next_dict.update({i:l for l in st for i in AB[l] if i not in already})
        next_st = set(next_dict.keys())
        # [already.add(k) for k in next_st]
        next_already = already.union(next_st)
        if len(next_already) == N:
            return next_dict
        elif len(next_st) == 0:
            print('No')
            exit()
        else:
            return serch(next_st, next_already, next_dict)

    ans = serch()
    print('Yes')
    [print(ans[i + 1]) for i in range(1, N)]

    # que = deque([1])
    # while que:
    #     deque.popleft(que)
    # print(AB)





if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    # AB = []
    # for _ in range(M):
    #     AB.append(list(map(int, input().split())))
    AB = {i+1:[] for i in range(N)}
    for _ in range(M):
        a, b = list(map(int, input().split()))
        AB[a].append(b)
        AB[b].append(a)
    main(AB, N, M)

Submission status: Runtime Error

Solution code:
import sys
n,m = map(int, sys.stdin.readline().rstrip("\n").split())
cage = {}
for i in range (2,n+1):
    cage[i] = None
ab = [map(int, line.rstrip("\n").split()) for line in sys.stdin]
a,b = [list(i) for i in zip(*ab)]
room = [1]
nroom = []
while None in cage.values():
    for i in range(len(room)):
        j = 0
        while j < (len(a)):
            if a[j] == room[i]:
                if cage[b[j]] == None:
                    cage[b[j]] = a[j]
                nroom.append(b[j])
                a.pop(j)
                b.pop(j)
            elif b[j] == room[i]:
                if cage[a[j]] == None:
                    cage[a[j]] = b[j]
                nroom.append(a[j])
                a.pop(j)
                b.pop(j)
            else:
                j += 1
    print(cage, room,nroom,a)
    if (len(a) == 0 and None in cage.values()) or room == nroom:
        print('No')
        break
    room = nroom[:]
    nroom.clear()
else:
    print('Yes')
    for i in range (2,n+1):
        print(cage[i])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g = [[] for _ in range(m)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
p = [0]*n
from collections import deque
q = deque([0])

while q:
  v = q.popleft()
  for i in g[v]:
    if p[i]<1:p[i]=v+1;q.append(i)
if 0 in p: print('No')
else:
  print('Yes')
  for v in p[1:]: print(v)

Submission status: Runtime Error

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

def g(j):
    for k in graph[j]:
        next = set()
        if 1 in graph[k]:
            return k
            next = set()
            break
            #print(j)
        else:
            next.add(k)
    if len(next) != 0:
        for l in next:
            g(l)

N,M = LI()
#print(N,M)
AB = list(LI() for _ in range(M))
#print(AB)

graph = {i:[] for i in range(1,N+1)}

for i in AB:
    a = i[0]
    b = i[1]
    graph[a] += [b]
    graph[b] += [a]

#print(graph)
print("Yes")
for i in range(2,N+1):
    #print(i)
    if 1 in graph[i]:
        print(1)
    else:
        print(g(i))

Submission status: Runtime Error

Solution code:
from collections import deque
def main():
  n,m=map(int,input().split())
  e=[[]for _ in range(n)]
  for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    e[a].appned(b)
    e[b].append(a)
  ans=[-1]*n
  dq=deque([0])
  while dq:
    g=dq.popleft()
    for v in e[g]:
      if ans[v]==-1:
        ans[v]=g+1
        dq.append(v)
  print(*ans[1:])
main()

Submission status: Runtime Error

Solution code:
from collections import deque

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

nodes = [ [] for i in range(m+1)]

# グラフ生成
for i in range(1, m + 1):
    a, b = map(int, input().split())
    nodes[a].append(b)
    nodes[b].append(a)

ans = [0] * (n+1)

# キュー作成
stk = deque([1])

# BFS 幅優先探索
while stk:
    v = stk.pop()
    for s in nodes[v]:
        # 未到達ノードであれば、キューに追加
        if ans[s] == 0:
            # ひとつ前のノードを記録
            ans[s] = v
            # キューに要素を追加
            stk.appendleft(s)

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

Submission status: Runtime Error

Solution code:
def input_from_console():
    n, m = map(int, input().split())
    ab_list = []
    for i in range(m):
        a,b = map(int, input().split())
        ab_list.append((a, b))
    return n, m, ab_list


class Graph(object):
    def __init__(self, edge_count):
        self.edge_count = edge_count
        self.graph = [set() for _ in range(self.edge_count + 1)]
        self.mark = [None for _ in range(self.edge_count + 1)]
        self.mark[1] = 1
        self.visit = [False for _ in range(self.edge_count + 1)]
        self.visit[0] = False
        self.visit[1] = False

    def add_edge(self, src, dest):
        self.graph[src].add(dest)
        self.graph[dest].add(src)

    def put_mark(self, pos):
        # check if already visit
        for mark in self.graph[pos]:
            if self.visit[mark]:
                continue
            if not self.mark[mark]:
                self.mark[mark] = pos

        for mark in self.graph[pos]:
            if self.visit[mark]:
                continue
            self.visit[mark] = True
            self.put_mark(mark)

    def check_connection(self):
        return any(self.visit[1:])



def solve(n, m, ab_list):
    result = ""

    graph = Graph(n)
    for (a, b) in ab_list:
        graph.add_edge(a, b)
    graph.put_mark(1)
    if graph.check_connection():
        result = "Yes\n"
        for item in graph.mark[2:]:
            result = result + str(item) + "\n"
    else:
        result = "No"
    return result


def main():
    n, m, ab_list = input_from_console()
    print(solve(n, m, ab_list))

# Adjascency List representation in Java

if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Runtime Error

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
n,m = map(int, input().split())		# 5 7 2


X = [0]*(n+1)


G = [ [] for _ in range(m+1) ]
for _ in range(m):
	a,b = map(int, input().split())		# 5 7 2
	G[a].append(b)
	G[b].append(a)


from collections import deque
Q = deque()
Q.append(1)

while Q:
	fm = Q.popleft()
	
	for to in G[fm]:
		
		if X[to]==0:
			X[to] = fm
			Q.append(to)

Y = X[2:]
for y in Y:
	print(y)

Submission status: Runtime Error

Solution code:

class Graph(object):
    def __init__(self, edge_count):
        self.edge_count = edge_count
        self.graph = [set() for _ in range(self.edge_count + 1)]
        self.mark = [None for _ in range(self.edge_count + 1)]
        self.mark[1] = 1
        self.visit = [False for _ in range(self.edge_count + 1)]
        self.visit[0] = False
        self.visit[1] = False

    def add_edge(self, src, dest):
        self.graph[src].add(dest)
        self.graph[dest].add(src)

    def put_mark(self, pos):
        # check if already visit
        for mark in self.graph[pos]:
            if self.visit[mark]:
                continue
            if not self.mark[mark]:
                self.mark[mark] = pos

        for mark in self.graph[pos]:
            if self.visit[mark]:
                continue
            self.visit[mark] = True
            self.put_mark(mark)

    def check_connection(self):
        return any(self.visit[1:])



def solve(n, m, ab_list):
    result = ""

    graph = Graph(n)
    for (a, b) in ab_list:
        graph.add_edge(a, b)
    graph.put_mark(1)
    if graph.check_connection():
        result = "Yes\n"
        for item in graph.mark[2:]:
            result = result + str(item) + "\n"
    else:
        result = "No"
    return result


def main():
    n, m, ab_list = input_from_console()
    print(solve(n, m, ab_list))

# Adjascency List representation in Java

if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Runtime Error

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

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

ans = [0]*(n+1)
flag = [0]*(n+1)
flag[1] = 1
que = [1]
while len(que) != 0:
    #print('que: ', len(que), que)
    now = que.pop()
    for to in dir[now]:
        if flag[to] == 1:
            continue
        que.append(to)
        flag[to] != 1
        ans[to] = now
"""         print(to)
        ans[to] = now
        flag[to] = 1
        for toto in dir[to]:
            if flag[toto] != 1:
                que.append(toto) """
print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Runtime Error

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

def g(j):
    for k in graph[j]:
        next = set()
        if 1 in graph[k]:
            return k
            next = set()
            break
            #print(j)
        else:
            next.add(k)
    if lem(next) != 0:
        for l in next:
            g(l)

N,M = LI()
#print(N,M)
AB = list(LI() for _ in range(M))
#print(AB)

graph = {i:[] for i in range(1,N+1)}

for i in AB:
    a = i[0]
    b = i[1]
    graph[a] += [b]
    graph[b] += [a]

#print(graph)
print("Yes")
for i in range(2,N+1):
    #print(i)
    if 1 in graph[i]:
        print(1)
    else:
        print(g(i))

Submission status: Runtime Error

Solution code:
from collections import deque

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

nodes = [ [] for i in range(m+1)]

# グラフ生成
for i in range(1, m + 1):
    a, b = map(int, input().split())
    nodes[a].append(b)
    nodes[b].append(a)

ans = [0] * (n+1)

# キュー作成
stk = deque([1])

# BFS 幅優先探索
while stk:
    v = stk.pop()
    for s in nodes[v]:
        # 未到達ノードであれば、キューに追加
        if ans[s] == 0:
            # ひとつ前のノードを記録
            ans[s] = v
            # キューに要素を追加
            stk.appendleft(s)

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

Submission status: Runtime Error

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
INF = 1e18+10

n = int(input())
a = [0 for i in range(n)]
b = [0 for i in range(n)]

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

graph = [[] for _ in range(n)]
value_indices = {} # a_b values
for i in range(n):
	if a[i] == 0 and b[i] == 0:
		for j in range(n):
			graph[i].append(j)
			graph[j].append(i)
	else:
		if a[i] == 0:
			a_b = 0
			m_b_a = INF
		elif b[i] == 0:
			a_b = INF
			m_b_a = 0
		else:
			a_b = a[i] / b[i]
			m_b_a = -b[i] / a[i]

		if m_b_a in value_indices:
			for j in value_indices[m_b_a]:
				graph[i].append(j)
				graph[j].append(i)
		value_indices[a_b] = value_indices.get(a_b, []) + [i]

# print("value_indices", value_indices)
# print("graph", graph)

def comb(i):
	# layers = []
	cur_layer = [i]
	next_layer = []
	used[i] = True

	chet = 0
	nechet = 0
	is_chet = True
	while len(cur_layer) > 0:
		if is_chet:
			chet += len(cur_layer)
		else:
			nechet += len(cur_layer)
		is_chet = not is_chet
		# layers.append(cur_layer)
		next_layer = []
		for item in cur_layer:
			for child in graph[item]:
				if not used[child]:
					next_layer.append(child)
					used[child] = True
		cur_layer = next_layer.copy()
	# print(layers)
	# for i in range(len(layers)):
	# 	if i % 2 == 0:
	# 		chet += len(layers[i])
	# 	else:
	# 		nechet += len(layers[i])
	return pow(2, chet, MODULO) + pow(2, nechet, MODULO) -1


ans = 1
used = [False for _ in range(n)]
for i in range(n):
	if not used[i]:
		if len(graph[i]) == 0:
			used[i]
			ans *= 2
			ans %= MODULO
		else:
			ans *= comb(i)
			ans %= MODULO
print(ans-1)

Submission status: Runtime Error

Solution code:
n, m = [int(v) for v in input().split()]
a, b = [], []
d = {}
for i in range(m):
    ai, bi = [int(v) for v in input().split()]
    a.append(ai)
    b.append(bi)
    d[ai] = d.get(ai, [])
    d[ai].append(bi)
    d[bi] = d.get(bi, [])
    d[bi].append(ai)

r = {}
def trace(no, lv):
    lst = d[no]
    for c in lst:
        if c != 1:
            if c not in r or (r[c][1] > lv and r[c][1] != 0):
                r[c] = (no, lv)
                trace(c, lv + 1)
trace(1, 1)

for i in range(2, n):
    if i not in r:
        print('No')
        break
else:
    print('Yes')
    for i in range(2, n +1):
        print(r[i][0])

Submission status: Runtime Error

Solution code:
from collections import deque

N,M = map(int,input().split())
adj = [[] for i in range(M)]

for _ in range(M):
    temp = list(map(int,input().split()))
    temp[0]-=1
    temp[1]-=1
    adj[temp[0]].append(temp[1])
    adj[temp[1]].append(temp[0])

visited = [0]*N
sirube = [-1]*N
d = deque()
def bfs():
    tmp = d.pop()
    for node in adj[tmp]:
        if visited[node] !=1:
            d.append(node)
            visited[node] = 1
            sirube[node] = tmp
d.append(0)       
while d:
    bfs()
print(sirube)
if -1 in sirube[1:N]:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(sirube[i]+1)

Submission status: Runtime Error

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

def g(j):
    for k in graph[j]:
        next = set()
        if 1 in graph[k]:
            return k
            break
            #print(j)
        else:
            next.add(k)
    if lem(next) != 0:
        for l in next:
            g(l)

N,M = LI()
#print(N,M)
AB = list(LI() for _ in range(M))
#print(AB)

graph = {i:[] for i in range(1,N+1)}

for i in AB:
    a = i[0]
    b = i[1]
    graph[a] += [b]
    graph[b] += [a]

#print(graph)
print("Yes")
for i in range(2,N+1):
    #print(i)
    if 1 in graph[i]:
        print(1)
    else:
        print(g(i))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [0]
b = [0]
for i in range(1, m+1):
    ta, tb = map(int, input().split())
    a.append(ta)
    b.append(tb)
dir = [[] for _ in range(m+1)]
for i in range(1, m+1):
    dir[a[i]].append(b[i])
    dir[b[i]].append(a[i])
ans = [0 for i in range(n+1)]
flag = [0 for i in range(n+1)]
flag[1] = 1
que = [1]
while len(que) != 0:
    #print('que: ', len(que), que)
    now = que.pop()
    for to in dir[now]:
        if flag[to] == 1:
            continue
        que.append(to)
        flag[to] != 1
        ans[to] = now
"""         print(to)
        ans[to] = now
        flag[to] = 1
        for toto in dir[to]:
            if flag[toto] != 1:
                que.append(toto) """
print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Runtime Error

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

dist = [-1] * (n + 1)
roots = [[] for i in range(n + 1)]

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

ans = [-1] * (n + 1)
ans[1] = 0
dist[1] = 0
q = deque()
q.append(1)

while q:
    now = q.popleft()

    for next_v in roots[now]:
        if not dist[next_v] == -1:
            continue
        dist[next_v] = dist[now] + 
        ans[next_v] = now
        q.append(next_v)
if -1 in ans[1:]:
    print('No')
else:
    print('Yes')
    for i in range(2, len(ans)):
        print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import deque

N,M = map(int,input().split())
adj = [[] for i in range(M)]

for _ in range(M):
    temp = list(map(int,input().split()))
    temp[0]-=1
    temp[1]-=1
    adj[temp[0]].append(temp[1])
    adj[temp[1]].append(temp[0])
INF = N*N
visited = [0]*N
sirube = [-1]*N
d = deque()

def bfs():
    tmp = d.pop()
    for node in adj[tmp]:
        if visited[node] !=1:
            d.append(node)
            visited[node] = 1
            sirube[node] = tmp
d.append(0)       
while d:
    bfs()
print(sirube)
if -1 in sirube[1:N]:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(sirube[i]+1)

Submission status: Runtime Error

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


route = {}

for i in range(M):
    A, B = [int(x) for x in input().split()]

    if A in route:
        route[A].append(B)
        #step[A] = -1
    else:
        route[A] = [B]    

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

step = {}
stepcount = 0
mark = {1: 0}
r = 1

def check(stepcount, r, mark):
    stepcount += 1
    if r in route:
        for nextr in route[r]:
            # print(nextr)
            # print(route[nextr])
            if nextr in step:
                # 既存のルートが有る
                if step[nextr] > stepcount:
                    # 今回のルートのほうが近い
                    step[nextr] = stepcount
                    mark[nextr] = r

            else:
                # ルートが無い
                step[nextr] = stepcount
                mark[nextr] = r
                check(stepcount, nextr, mark)

check(0, 1, mark)
import time
time.sleep(2)
# print(step)
# print(route)
# print(mark)

if len(mark) == N:
    print('Yes')
    for i in range(2, N + 1):
        print(mark[i])
else:
    print('No')

Submission status: Runtime Error

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

def g(i):
    for j in graph[i]:
        next = set()
        if 1 in graph[j]:
            return j
            break
            #print(j)
        else:
            next.add(j)
    if lem(next) != 0:
        for k in next:
            g(k)

N,M = LI()
#print(N,M)
AB = list(LI() for _ in range(M))
#print(AB)

graph = {i:[] for i in range(1,N+1)}

for i in AB:
    a = i[0]
    b = i[1]
    graph[a] += [b]
    graph[b] += [a]

#print(graph)
print("Yes")
for i in range(2,N+1):
    #print(i)
    if 1 in graph[i]:
        print(1)
    else:
        print(g(i))

Submission status: Runtime Error

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

from collections import deque
q = deque([0])
p = [0]*n
while len(q)>0:
  v = q.popleft()
  for i in g[v]:
    if p[i]==0:p[i]=v+1;q.append(i)
if 0 in p: print('No')
else:
  print('Yes')
  for v in p[1:]:print(v)