Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import defaultdict, deque

d = ' '
n, q = map(int, input().split(d))

tree = defaultdict(lambda: [])
for _ in range(n - 1):
    a, b = map(int, input().split(d))
    tree[a].append(b)
    tree[b].append(a)

count = defaultdict(lambda: 0)
for _ in range(q):
    p, x = map(int, input().split(d))
    count[p] += x

ret = [0] * n
q = deque(maxlen=n)
q.append((1, 1))
while len(q) > 0:
    f, c = q.popleft()
    ret[c - 1] = count[c] + ret[f - 1]
    for n in tree[c]:
        if n != f:
            q.append((c, n))

print(*ret)


### FIXED CODE ###

from collections import defaultdict, deque

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

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

count = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    count[p - 1] += x

ret = [0] * n
q = deque(maxlen = n)
q.append((0, 0))
while len(q) > 0:
    f, c = q.popleft()
    ret[c] = count[c] + ret[f]
    for n in tree[c]:
        if n != f:
            q.append((c, n))

print(*ret)
### BUGGY CODE ###

def main():
    s = input()
    ss = s
    for i in range(len(s)//2):
        f = len(ss)
        ss = ss.replace("01", "").replace("10", "")
        if f == len(ss):
            break
    print(len(s)-len(ss))
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

s=input()
zero = s.count("0")
one = s.count("1")
print(len(s)-abs(zero-one))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
  
s = [0]*N
for i in range(N):
  s[i] = S[0:i+1:].count("AC")
    
for _ in range(Q):
  l, r = map(int, input().split())
  print(s[r-1] - s[l-1])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
  
ac_sum = [0]*N
for i in range(N):
  if S[max(i-1,0):i+1] == "AC":
    ac_sum[i] = ac_sum[max(i-1,0)] + 1
  else:
    ac_sum[i] = ac_sum[max(i-1,0)]

for _ in range(Q):
  l, r = map(int, input().split())
  print(ac_sum[r-1] - ac_sum[l-1])
### BUGGY CODE ###

def main():
    n = int(input())
    a = list( map( int, input().split()))
    sum = 1
    for i in a:
        sum = sum * i
    if sum >1000000000000000000:
        print(-1)
    else:
       print(sum)
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

import copy

def main():
    n = int(input())
    a = list( map( int, input().split()))
    sum = 1
    if 0 in a:
        print(0)
    else:
        for i in a:
            sum = sum * i
            if sum > 1000000000000000000:
                print(-1)
                exit()
        print(sum)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -float("inf")
for start in range(N):
    x = start
    cyc_score = []
    total_cyc_score = 0
    while True:
        x = P[x]-1
        cyc_score.append(C[x])
        total_cyc_score += C[x]
        if x == start: # 周期を検出
            break
    t = 0
    for i in range(len(cyc_score)):
        t += cyc_score[i]
        if i + 1 > K: break
        now_score = t
        if total_cyc_score > 0:
            e = int((K - i - 1) / len(cyc_score))
            now_score += total_cyc_score * e
        ans = max(ans, now_score)
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -float("inf")
for start in range(N):
    x = start
    cyc_score = []
    total_cyc_score = 0
    while True:
        x = P[x]-1
        cyc_score.append(C[x])
        total_cyc_score += C[x]
        if x == start: # 周期を検出
            break
    t = 0
    for i in range(len(cyc_score)):
        t += cyc_score[i]
        if i + 1 > K: break
        now_score = t
        if total_cyc_score > 0:
            e = int((K - i - 1) / len(cyc_score))
            now_score += total_cyc_score * e
        ans = max(ans, now_score)
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
scores=[]
for i in range(N-K+1):
  score=1
  for j in range(i,i+K):
    score*=A[j]
  scores.append(score)

for i in range(len(scores)-1):
  if scores[i+1]>scores[i]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(N-K):
  if A[i]<A[i+K]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
max_A = max(A)
for i in range(N):
    if A[i] == max_A:
        print(max(A[:i]+A[i+1:]))
    else:
        print(max_A)
    

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
sortA = sorted(A, reverse=True)
for i in range(N):
    if A[i] == sortA[0]:
        print(sortA[1])
    else:
        print(sortA[0])
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

"""
nC3
|b - c| < a < |b + c|

nC2
b_i, c_iを除くiの中で|b-c|< a <b+cを満たすaの数をタス
"""

N = int(input())
L = LI()
L.sort()

ans = 0
for i in range(N - 1, -1, -1):
    for j in range(i - 1, -1, -1):
        # print(i, j)
        a,b = L[i], L[j]
        # print(L[:j])
        # print(bisect.bisect_right(L[:j], a- b))
        ans += j - bisect.bisect_right(L[:j], a- b)
        # ans += bisect.bisect_right(L[:j], a-b) - bisect.bisect_left(L[:j], a-b)
print(ans)




### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

"""
nC3
|b - c| < a < |b + c|

nC2
b_i, c_iを除くiの中で|b-c|< a <b+cを満たすaの数をタス
"""

N = int(input())
L = LI()
L.sort()

ans = 0
for i in range(N - 1, -1, -1):
    for j in range(i - 1, -1, -1):
        ans += j - bisect.bisect_right(L[:j], L[i] - L[j])
print(ans)
### BUGGY CODE ###

import itertools

N = int(input())
L = [int(a) for a in input().split()]

comb_sides = list(itertools.combinations(L, 3))

num_triangles = 0
for sides in comb_sides:
    if sides[0] + sides[1] > sides[2] and sides[1] + sides[2] > sides[0] and sides[2] + sides[0] > sides[1]:
        num_triangles += 1

print(num_triangles)


### FIXED CODE ###

import bisect

N = int(input())
L = [int(a) for a in input().split()]

L.sort()

num_triangles = 0
for i in range(0, N - 2): # 0, 1, ..., N - 3
    for j in range(i + 1, N - 1): # i+1, i+2, ..., N-2
        num_triangles += bisect.bisect_left(L[j + 1:N], L[i] + L[j])

print(num_triangles)
### BUGGY CODE ###

import itertools

n = int(input())
L = list(map(int, input().split()))

ans = 0
for a, b, c in itertools.combinations(L, 3):
    if a < b + c and b < c+a and c < a+b:
        ans += 1
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
L = list(map(int, input().split()))

ans = 0
L.sort()

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        idx = bisect.bisect_left(L, L[i] + L[j])
        ans += max(0, idx - j - 1)
print(ans)
### BUGGY CODE ###

s=input()

cnt=0
while(True):
  if s.find("ABC") == -1:
    break
  else:
    s = s.replace("ABC","BCA",1)
    cnt += 1
    
print(cnt)

### FIXED CODE ###

s=input()

s2list=list(s.replace("BC","D"))
#print(s2list)

block_list=[]
bl=[]
for s2 in s2list:
  if s2=="A" or s2=="D":
    bl.append(s2)
  else:
    if len(bl)>0:
      block_list.append("".join(bl))
      bl=[]
else:
  if len(bl)>0:
    block_list.append("".join(bl))
#print(block_list)

answer=0
for bl in block_list:
  #print(bl)
  cnt_a=0
  for c in bl:
    if c=="A":
      cnt_a+=1
    else:
      answer+=cnt_a
    
print(answer)
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))


    class RangeMinimumQuery:
        def __init__(self, n, inf=2 ** 31 - 1):
            self.n = 1 << (n - 1).bit_length()
            self.INF = inf
            self.segtree = [self.INF] * (2 * self.n)

        # i番目の値(0-indexed)をxに変更
        def update(self, i, x):
            i += self.n
            self.segtree[i] = x
            while i > 0:
                i //= 2
                self.segtree[i] = min(self.segtree[2 * i], self.segtree[2 * i + 1])

        # [l, r)のmin
        def query(self, l, r):
            L, R = l + self.n, r + self.n
            R = min(R, len(self.segtree))
            s = self.INF
            while L < R:
                if L & 1:
                    s = min(s, self.segtree[L])
                    L += 1

                if R & 1:
                    s = min(s, self.segtree[R - 1])
                    R -= 1

                L >>= 1
                R >>= 1

            return s


    # 番兵を設置
    A = [0] + A + [0]
    N = N + 2


    # セグ木を初期化
    RMQ = RangeMinimumQuery(N)
    for i, a in enumerate(A):
        RMQ.update(i, a)


    # r_indexes := 自分より右側であって、最も近い、自分より小さなもののindex
    # l_indexes := 自分より左側であって、最も近い、自分より小さなもののindex
    r_indexes = [None] * N
    l_indexes = [None] * N


    # 右側についてにぶたん := iからm内の区間最小値がai以上か？
    for i, a in enumerate(A[1: -1], start=1):
        ok, ng = i, N - 1
        while abs(ok - ng) > 1:
            m = (ok + ng) // 2

            if a <= RMQ.query(i, m + 1):
                ok = m
            else:
                ng = m

        r_indexes[i] = ok + 1

    # 左側についてにぶたん := iからm内の区間最小値がai以上か？
    for i, a in enumerate(A[1: -1], start=1):
        ok, ng = i, 0
        while abs(ok - ng) > 1:
            m = (ok + ng) // 2

            if a <= RMQ.query(m, i + 1):
                ok = m
            else:
                ng = m

        l_indexes[i] = ok - 1


    # 答えを計算
    ans = 0
    for i, (a, l, r) in enumerate(zip(A[1: -1], l_indexes[1: -1], r_indexes[1: -1]), start=1):
        ans += a * (i - l) * (r - i)

    print(ans)


### FIXED CODE ###

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

d = [0] * (N+1)
for i in range(N):
    d[a[i]] = i

left = list(range(N+1))
right = list(range(N+1))

ans = 0
for i in range(N, 0, -1):
    di = d[i]
    ans += i * (right[di]-di+1) * (di-left[di]+1)
    right[left[di] - 1] = right[di]
    left[right[di] + 1] = left[di]

print(ans)
### BUGGY CODE ###

n=int(input())
s_list=[]
unq_list=[]
count=0
for i in range(n):
  s_elem=''.join(sorted(list(input())))
  s_list.append(s_elem)
  if s_list.count(s_elem) > 1:
    count+=s_list.count(s_elem)-1

print(count)

### FIXED CODE ###

n=int(input())
dic={}

count=0
for i in range(n):
  s_elem=''.join(sorted(list(input())))
  if s_elem in dic:
    count+=dic[s_elem]
    dic[s_elem]+=1
  else:
    dic[s_elem]=1

print(count)
### BUGGY CODE ###

import math
import queue
import bisect
import heapq

mod = 1e9+7

def swap(a,b):
    return (b,a)

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,a,2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
        if prime:
            pn.append(i)
    return pn

def main():
    a,b = map(int,input().split())
    g = gcd(a,b)
    g_l = divisors(g)
    pn = prime_num(max(g_l)+1)
    ans = 1
    for i in g_l:
        if i in pn:
            ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
import queue
import bisect
import heapq
import time

mod = 1e9+7

def swap(a,b):
    return (b,a)

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def main():
    a,b = map(int,input().split())
    g = gcd(a,b)
    g_l = divisors(g)
    ans = 1
    for i in g_l:
        if is_prime(i):
            ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
ans = 0
for i in range((n//r)+1):
    for j in range((n//g)+1):
        temp = (n - i * r - j * g)
        if temp >=0 and temp % b == 0:
            ans += 1
print(ans)


### FIXED CODE ###

r, g, b, n = map(int, input().split())
ans = 0
for i in range((n//r)+1):
    for j in range((n//g)+1):
        temp = (n - i * r - j * g)
        if temp >=0 and temp % b == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

import sys
n, k = map(int, input().split())
w = tuple(map(int, sys.stdin.readlines()))
p = max(w)
s = sum(w)
if n <= k:
    print(p)
elif k == 1:
    print(s)
else:
    a = max(p, s//k)
    while True:
        l = [a]
        for i in range(n):
            d = l[-1] - w[i]
            if d < 0:
                l.append(a-w[i])
            else:
                l[-1] = d
            i += 1
        if len(l) > k:
            a += 1
        else:
            break
    print(a)

### FIXED CODE ###

n,k = map(int, input().split())
w = [int(input()) for _ in range(n)]

def check(p):
    c = t = 0
    for wi in w:
        t += wi
        if t > p:
            t = wi
            c += 1
            if c >= k:
                return False
    return True

s = max(w)
l = sum(w)
while s < l:
    m = (s+l)//2
    if check(m):
        l = m
    else:
        s = m = m+1
print(s)
### BUGGY CODE ###

def binary(x):
    '''40桁の2進数表記の作成'''

    k = 40
    s = ''
    for i in reversed(range(k)):
        s += str(x // 2 ** i)
        x %= 2 ** i

    return s

def decimal(s):
    '''40桁の2進数を10進数に変換'''

    k = 40
    x = 0
    for i in range(k):
        x += int(s[i]) * 2 ** (k - 1 - i) 

    return x

def xor(x, y):
    '''xor calcuration'''

    bx = binary(x)
    by = binary(y)
    s = ''

    for i in range(len(bx)):
        if abs(int(bx[i]) - int(by[i])):
            s += '1'
        else:
            s += '0'
    return decimal(s)

def f(x, a):
    '''f(x) calcuration'''

    fx = 0
    for i in a:
        fx += xor(x, i)

    return fx

# 未知のxkを既知のkkに置き換える
# k += 1 として、x < k を満たす
# この時、xの未知の40桁のいくつかを、既知のkで置き換える
n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

ck = [0 for i in range(40)]
for i in a:
    ab = binary(i)
    for j in range(40):
        ck[j] += int(ab[j])


k1b = binary(k + 1)

for i in reversed(range(len(k1b))):
    if k1b[-i-1] == '1':
        lenk = i
        break

fx = []
for i in reversed(range(lenk + 1)):
    x = ''
    for j in reversed(range(40)):
        if j > i:
            x += str(int(k1b[-j-1]))
        elif j == i:
            if k1b[-j-1] == '1':
                x += str(0)
            else:
                break
        else:
            if ck[-j-1] * 2 > n:
                x += str(0)
            else:
                x += str(1)

    if len(x) == 40:
        x = decimal(x)
        fx.append(f(x, a))

print(max(fx))


### FIXED CODE ###

# bit演算という方法がある、ビット演算子
# a & b 1,1で1
# a | b 1,1, 1,0, 0,1で1
# a ^ b xor
# ~a ビット反転
# << 左シフト
# >> 右シフト
# 未知のxkを既知のkkに置き換える
# k += 1 として、x < k を満たす
# この時、xの未知の40桁のいくつかを、既知のkで置き換える
# 注意として、xはkより大きくなってはいけない

n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

ck = [0 for i in range(40)]
for i in a:
    for j in range(40):
        if i>>j & 1:
            ck[j] += 1

fx = []
for i in range(40):

    if (k+1)>>i & 1 == 0:
        continue

    ans = 0
    for j in range(40):
        if j > i:
            if ((k+1)>>j) & 1:
                ans += (1<<j) * (n-ck[j])
            else:
                ans += (1<<j) * ck[j]
        elif j == i:
            ans += (1<<j) * ck[j]
        else:
            if ck[j] * 2 > n:
                ans += (1<<j) * ck[j]
            else:
                ans += (1<<j) * (n-ck[j])

    fx.append(ans)

print(max(fx))
### BUGGY CODE ###

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

count = 1

for i in range(1, len(P)):
    if min(P[:i]) >= P[i]:
        count += 1

print(count)

### FIXED CODE ###

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

count = 1
m = P[0]
for i in range(1, len(P)):
    m = min(m, P[i - 1])
    if m >= P[i]:
        count += 1

print(count)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
max_num = max(A)
result = [max(A[:i]+A[i+1:]) for i in range(N)]
for i in range(N):
  print(result[i])

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]

max_num = max(A)
a = sorted(A)
second = a[-2]

for i in range(N):
    if A[i] == max_num:
        print(second)
    else:
        print(max_num)
### BUGGY CODE ###

x, y, z, K = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)


def check(P):
    cnt = 0
    for i in range(x):
        for j in range(y):
            for k in range(z):
                if A[i]+B[j]+C[k] < P:
                    break
                cnt += 1
                if K <= cnt:
                    return True
    return False


L = 1
R = 10**14
while L != R-1:
    M = (L+R)//2
    if check(M):
        L = M
    else:
        R = M

ans = []
for i in range(x):
    for j in range(y):
        for k in range(z):
            if A[i]+B[j]+C[k] <= L:
                break
            ans.append(A[i]+B[j]+C[k])

ans.sort(reverse=True)
for i in range(K):
    if i < len(ans):
        print(ans[i])
    else:
        print(L)

### FIXED CODE ###

from itertools import product
x, y, z, k = map(int, input().split())
A = map(int, input().split())
B = map(int, input().split())
C = map(int, input().split())
AB = [sum(ab) for ab in product(A, B)]
AB.sort(reverse=True)
AB = AB[:k]
ABC = [sum(abc) for abc in product(AB, C)]
ABC.sort(reverse=True)
for i in range(k):
    print(ABC[i])
### BUGGY CODE ###

h,n = map(int,input().split())
inf = 1000000000
res = inf
dp = [inf] * (h + 1)
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(h):
        to = min(j + a,h)
        dp[to] = min(dp[to],dp[j] + b)
print(dp[h])


### FIXED CODE ###

h,n = map(int,input().split())
len = h + 10005
inf = 1000000000
res = inf
dp = [inf] * len
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(len):
        if j >= a:
            dp[j] = min(dp[j],dp[j-a] + b)
        if j >= h:
            res = min(res,dp[j])
print(res)
### BUGGY CODE ###

MOD = 1000000007
n = int(input())
aas = list(map(int, input().split()))
res = 0
for i in range(n-1):
    for j in range(i,n):
        res += (aas[i]^aas[j]) % MOD
        res %= MOD
print(res)

### FIXED CODE ###

MOD = 1000000007
n = int(input())
aas = list(map(int, input().split()))
KET = 60
arr_0 = [0]*KET
arr_1 = [0]*KET
for i in aas:
    bits = format(i,'060b')
    for j in reversed(range(KET)):
        if bits[j] == '0':
            arr_0[KET-j-1] += 1
        else:
            arr_1[KET-j-1] += 1
res = 0
for i in range(KET):
    res += (arr_0[i]%MOD * arr_1[i]%MOD)%MOD * pow(2,i,MOD)
    res %= MOD
print(res)
### BUGGY CODE ###

import heapq
f=lambda:map(int,input().split())
V,E,L=f()
G=[[] for _ in [0]*(V+1)]
# G=[]

for _ in range(E):
    s,t,d=f()
    if d<=L:
        G[s].append((t,(0,d)))
        G[t].append((s,(0,d)))
    
INF=float('inf')

def dijk(s):
    q=[((INF,INF),i) for i in range(V+1)]
    # q[i]:点i+1の現状のコスト
    q[s]=((0,0),s)
    heapq.heapify(q)

    res=[(INF,INF)]*(V+1)
    while q:
        C,p=heapq.heappop(q)
        if C<res[p]:
            res[p]=C
        else:
            continue
        for np,D in G[p]:
            costA=res[np]
            d=D[1]+C[1]
            if d>L:
                costB=(1+C[0]+D[0],D[1])
            else:
                costB=(C[0]+D[0],d)
            heapq.heappush(q,(min(costA,costB),np))
    return res

res=[0]+[dijk(i+1) for i in range(V)]

Q=int(input())
for _ in [0]*Q:
    s,t=f()
    r=res[s][t][0]
    print(r if r<INF else -1)

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

f=lambda:map(int,input().split())
N,M,L=f()
G=[[0]*N for _ in [0]*N]
for _ in [0]*M:
    a,b,c=f()
    G[a-1][b-1]=c
    G[b-1][a-1]=c
    
csr=csr_matrix(G)

D=floyd_warshall(csr)
INF=float('inf')
G=[[INF]*N for _ in [0]*N]
for i in range(N):
    for j in range(N):
        if i!=j and D[i][j]<=L:
            G[i][j]=1
            G[j][i]=1
csr=csr_matrix(G)
res=floyd_warshall(csr)
Q=int(input())
for _ in [0]*Q:
    s,t=f()
    r=res[s-1][t-1]
    print(int(r-1) if r<INF else -1)
### BUGGY CODE ###

N=int(input())
A=[int(x) for x in input().split()]
l=[0]
c=0

if 1 not in A:
    print(-1)
    exit()


for i in range(N-1):
    if A[i] in l or l[c]+1 != A[i]:
        continue

    else:
        l.append(A[i])
        c+=1

if l[-1]+1==A[-1]:
    l.append(A[-1])
print(N+1-len(l))


### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]
ne=1
c=0

if 1 not in A:
    print(-1)
    exit()


for i in range(N-1):
    if A[i]==ne:
        c+=1
        ne+=1
if A[-1]==ne:
    c+=1
print(N-c)
### BUGGY CODE ###

n = int(input())

a = list(map(int, input().split()))
cnt = 0
b = 0
for i in range(n):
    b += a[i]
    if b == 0:
        cnt += 1
    c = b
    for j in range(i):
        c -= a[j]
        if c == 0:
            cnt +=1
            
print(cnt)

### FIXED CODE ###


n = int(input())

a = list(map(int, input().split()))
cnt = 0
b = 0
c = [0]
for i in range(n):
    b += a[i]
    c.append(b)

c.sort()
i=0
ncm=0
m = 1
while True:
    i += 1
    if i == n+1:
        ncm += m*(m-1)//2
        break        
    if c[i] == c[i-1]:
        m += 1
        continue
    else:
        ncm += m*(m-1)//2
        m = 1

print(ncm)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
adj = [[float("inf") for i in range(N)] for j in range(N)]
signs = [-1 for i in range(N)]
signs[0] = 1

for _ in range(M):
  x,y = map(int,input().split())
  adj[x - 1][y - 1] = 1
  adj[y - 1][x - 1] = 1

queue = deque([0])
dist = 0

while len(queue) > 0:
  cur = queue.popleft()
  for i, c in enumerate(adj[cur]):
    if c == 1:
      if signs[i] == -1:
        queue.append(i)
        signs[i] = cur

if all([sign != -1 for sign in signs]):
  print("Yes")
  for sign in signs[1:]:
    print(sign + 1)
else:
  print("No")

### FIXED CODE ###

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

adj = [[] for i in range(N)]
signs = [-1 for i in range(N)]
# not_patrolled = set(range(1, N))

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

queue = deque([0])

while len(queue) > 0:
  cur = queue.popleft()
  for i in adj[cur]:
    if signs[i] == -1:
      queue.append(i)
      signs[i] = cur
      # not_patrolled.remove(i)

if all([sign != -1 for sign in signs[1:]]):
  print("Yes")
  for sign in signs[1:]:
    print(sign + 1)
else:
  print("No")