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

import sys
sys.setrecursionlimit(10**7)

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

# 木構造をリストで表現する
G = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

# 各操作で与えられる値を、各頂点ごとに集計しておく
P = [0] * (N+1)
for i in range(Q):
    p, x = map(int, input().split())
    P[p] += x


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとする
    P[v] += point

    for next_v in G[v]:
        if next_v == parent:
            continue
        dfs(next_v, v, P[v])


dfs(1, 0, 0)

res = ' '.join(map(str, P[1:]))
print(res)

### FIXED CODE ###

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

 
N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in PX:
    value[p] += x
 
def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])
 
dfs(1,0,0)
 
answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

s = list(input())
l = len(s)
i = 0
while True:
    if len(s)-1 <= i:
        break
    if s[i] == '0' and s[i+1] == '1' or s[i] == '1' and s[i+1] == '0':
        del s[i:i+2]
        i = 0
    else:
        i += 1

print(l-len(s))


### FIXED CODE ###

s = list(input())
print(min(s.count('0'), s.count('1'))*2)
### BUGGY CODE ###

N = int(input())
C = list(input())
import copy
D = []
flag = 0
ans = 0

for p in range(N):
    if C[p] == "R":
        D += ["0"]
    else:
        D += ["1"]



def change(x,y):
    global ans
    hoge = copy.deepcopy(D[x])
    D[x] = D[y]
    D[y] = hoge
    ans += 1

def color(x):
    global ans
    ans += 1
    if D[x] == "0":
        D[x] = "1"
    elif D[x] == "1":
        D[x] = "0"

while flag == 0:
    for q in range(N):
        if D[q] == "1":
            for s in range(N):
                if D[N-s-1] =="0" :
                    if q < N-s-1:
                        change(q,N-s-1)
                    break
        else:
            continue
        break

    for r in range(N):
        if int("".join(D),2) == 2**r-1:
            flag = 1

print(ans)


### FIXED CODE ###

N = int(input())
C = list(input())
import copy
D = []
flag = 0
ans = 0
keisan = 0

for p in range(N):
    if C[p] == "R":
        D += ["0"]
    else:
        D += ["1"]



def change(x,y):
    global ans
    hoge = copy.deepcopy(D[x])
    D[x] = D[y]
    D[y] = hoge
    ans += 1

def color(x):
    global ans
    ans += 1
    if D[x] == "0":
        D[x] = "1"
    elif D[x] == "1":
        D[x] = "0"

zero = D.count("0")
ichi = D.count("1")

for p in range(zero):
    if D[p] == "1":
        ans += 1


"""
while flag == 0:

    for r in range(N):
        if int("".join(D),2) == 2**r-1:
            flag = 1

    if flag == 0:
        for q in range(N):
            if D[q] == "1":
                for s in range(N):
                    keisan += 1
                    if D[N-s-1] =="0" :
                        if q < N-s-1:
                            change(q,N-s-1)
                        break
            else:
                continue
            break
"""
print(ans)
### BUGGY CODE ###

from collections import defaultdict
n = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")
for i in range(n):
    for r in range(1,n):
        if i + r < n and 0 <= i - r:
            if S[i + r] != S[i - r] and S[i] != S[i - r]and S[i] != S[i + r]:
                ans -=1

print(ans)


### FIXED CODE ###

from collections import defaultdict
n = int(input())
S = input()
patterns = ["RGB","RBG","GBR","GRB","BRG","BGR"]
acc  = [ [0] * (n + 1) for _ in range(n+1)]

ans = 0
for pattern in patterns:
    c1 = pattern[0]
    c2 = pattern[1]
    c3 = pattern[2]
    cands = []
    #i c1の位置で
    for i1 in range(n):
        for i2 in range(i1 + 1,n):
            if S[i1] == c2 and S[i2] == c3:
                cands.append((i1,i2-i1))
    # anss[i1][i2-i1]→左をi1に固定したときの、距離i2-i1の組の個数
    cands.reverse()
    di = defaultdict(lambda :set())
    for cand in cands:
        left,dist = cand
        di[left].add(dist)
    acc = [0]
    for i in range(1,n):
        acc.append(acc[i-1] + len(di[i]))

    for  i in range(0,n):
        if S[i] == c1:
            ans += acc[n - 1] -acc[i]
            for i2 in range(i + 1,n):
                if i2 - i in di[i2]:
                    ans -=1
print(ans)
### BUGGY CODE ###

def readinput():
    n=int(input())
    x=input()
    return n,x


def popcount(n):
    binn=bin(n)
    return binn.count('1')

def f(n):
    #print(n)
    if n==0:
        return 0
    else:
        m=n%popcount(n)
        return f(m)+1

def main(n,x):
    intx=int(x,2)
    ans=[]
    b=1
    for i in range(n):
        y=intx^b
        ans.append(f(y))
        b=b*2
    return reversed(ans)

def makeFtbl(n):
    Ftbl=[0]*(n+1)
    Ftbl[1]=1
    Ftbl[2]=1
    for i in range(3,n+1):
        m=i%popcount(i)
        Ftbl[i]=Ftbl[m]+1
    return Ftbl

def main2(n,x):
    Ftbl=makeFtbl(n)
    intx=int(x,2)
    return [0]

popinit=False
popdict={}
def popcounts(x):
    global popinit
    global popdict
    '''文字列xに含まれる'1'の数を返す
    '''
    if x.find('0b')!=-1:
        x=x[2:]
    if not popinit:
        popdict[x]=x.count('1')
        for i in range(len(x)):
            ibit=int(x[i],2)
            jbit=ibit^1
            y=x[:i]+str(jbit)+x[i+1:]
            if ibit==1:
                popdict[y]=popdict[x]-1
            else:
                popdict[y]=popdict[x]+1
        popinit=True
    if x in popdict.keys():
        return popdict[x]
    else:
        return x.count('1')

def fs(n):
    #print(n)
    if n==0:
        return 0
    else:
        binn=bin(n)[2:]
        m=n%popcounts(binn)
        return fs(m)+1

def main3(n,x):
    intx=int(x,2)
    ans=[]
    b=1
    for i in range(n):
        y=intx^b
        ans.append(fs(y))
        b=b*2
    return reversed(ans)

if __name__=='__main__':
    n,x=readinput()
    ans=main3(n,x)
    for a in ans:
        print(a)

### FIXED CODE ###

def readinput():
    n=int(input())
    x=input()
    return n,x

poptbl=[0]*(2*10**5+1)
def popcount(x):
    global poptbl
    if poptbl[x]!=0:
        return poptbl[x]
    
    poptbl[x]=bin(x).count('1')
    return poptbl[x]

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    if ftbl[x]!=0:
        return ftbl[x]
    
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        ftbl[x]=ans
        return ans    

def main():
    n=int(input())
    x=input()
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    pow2mod1=[0]*n
    pow2mod2=[0]*n
    pow2mod1[0]=1
    pow2mod2[0]=1
    for i in range(1,n):
        if m!=1:
            pow2mod1[i]=pow2mod1[i-1]*2 % (m-1)
        pow2mod2[i]=pow2mod2[i-1]*2 % (m+1)

    ans=[]
    #b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                a=0
                ans.append(a)
            else:
                xx=( xmodm1 + (m-1) -pow2mod1[n-i-1] )%(m-1)
                #ans.append(f(xx)+1)
                a=f(xx)+1
                ans.append(a)
        else:
            xx=( xmodp1 + pow2mod2[n-i-1] )%(m+1)
            #ans.append(f(xx)+1)
            a=f(xx)+1
            ans.append(a)
        #b=b//2
        print(a)
    return ans

if __name__=='__main__':
    #n,x=readinput()
    ans=main()
    #for a in ans:
    #    print(a)
### BUGGY CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
if K >= N:
    print(0)
else:
    for _ in range(K):
        H.pop(H.index(max(H)))
    print(sum(H))

### FIXED CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
H.sort(reverse=True)
if K >= N:
    print(0)
else:
    print(sum(H[K:]))
### BUGGY CODE ###

N = int(input())
A = []
import sys
input = sys.stdin.readline
for i in range(N):
  A.append(int(input().rstrip()))
from collections import Counter
counter = Counter(A)
B = sorted(set(A), key = A.index)
B = sorted(B, reverse = True)
max_A = B[0]
try:
  second_max = B[1]
except:
  second_max = B[0]
j = False
if counter[max_A] >= 2:
  j = True
for i in range(N):
  if A[i] == max_A and j == False:
    print(second_max)
  else:
    print(max_A)

### FIXED CODE ###

N = int(input())
A = []
import sys
input = sys.stdin.readline
for i in range(N):
  A.append(int(input().rstrip()))
from collections import Counter
counter = Counter(A)
max_A = max(A)
#B = sorted(set(A), key = A.index)
#B = sorted(B, reverse = True)
#max_A = B[0]
try:
  second_max = sorted(set(A))[-2]
except:
  second_max = max_A
j = False
if counter[max_A] >= 2:
  j = True
for i in range(N):
  if A[i] == max_A and j == False:
    print(second_max)
  else:
    print(max_A)
### BUGGY CODE ###

#https://atcoder.jp/contests/tenka1-2019-beginner/tasks/tenka1_2019_c

N = int(input())
S = str(input())
Sarray = list(S)
Sarraynum = []

#白0
for i in range(len(Sarray)):
    if Sarray[i] == '.':
        Sarraynum.append(0)
    else:
        Sarraynum.append(1)

white2black = len(Sarraynum)
black2white = len(Sarraynum)
for i in range(len(Sarraynum)):
    black2whiteTMP = 0
    white2blackTMP = len(Sarraynum) - i - 1
    for j in range(i):
        black2whiteTMP += Sarraynum[j]
    for j in range(i + 1, len(Sarraynum)):
            white2blackTMP -= Sarraynum[j]
    if black2whiteTMP + white2blackTMP < white2black + black2white:
        white2black = white2blackTMP
        black2white = black2whiteTMP


print(white2black + black2white)

### FIXED CODE ###

N = int(input())
S = str(input())
Sarray = list(S)

white = 0 #にしなきゃ
black = 0 #にしなきゃ
for i in range(len(Sarray)):
    if Sarray[i] == '.':
        black += 1

a = [white + black]
for i in range(len(Sarray)):
    if Sarray[i] == '.':
        black -= 1
    else:
        white += 1
    a.append(white + black)
a.sort()
print(a[0])
### BUGGY CODE ###

import numpy as np
n = int(input())
A = np.array(list(map(int, input().split())))
B = np.array(list(map(int, input().split())))
C = np.array(list(map(int, input().split())))

ans = 0
for a in A:
    for b in B[B>a]:
        ans += sum(C>b)
        
print(ans)

### FIXED CODE ###

import numpy as np
import bisect
n = int(input())
A = sorted(list(map(int, input().split())))
B = list(map(int, input().split()))
C = sorted(list(map(int, input().split())))

ans = 0
for b in B:
    ans += bisect.bisect_left(A, b) * (n - bisect.bisect_right(C, b))
print(ans)
### BUGGY CODE ###

def check(s_i, n_i, count, i_set):
    for i in range(9):
        i_set_tmp = set(i_set)
        if i not in i_set:
            continue
        if s_i == 0 and n_i == 0:
            return count + 1
        elif s_i < 0 or n_i < 0:
            break
        else:
            s_tmp = s_i - i*n_i
            n_tmp = n_i - 1
            i_set_tmp.remove(i)
            count = check(s_tmp, n_tmp, count, i_set_tmp)
    return count

i_list = [i for i in range(10)]
while True:
    try:
        n, s = map(int, input().split())
        ans = check(s, n, 0, set(i_list))
        print(ans)
    except:
        break



### FIXED CODE ###

s_max = [0]
for i in range(1,11):
    s = 0
    for j in range(i):
        s += (10 - j - 1)*(i - j)
    s_max.append(s)

def check(u, r, s, m):
    if r == 0:
        return s == 0
    n = 0
    for i in range(10):
        n *= 2
        if u[i]:
            n += 1
    if (n, r, s) in m:
        return m[(n, r, s)]
    if s < 0 or s > s_max[r]:
        return 0

    ans = 0
    for i in range(10):
        if not u[i]:
            u[i] = True
            ans += check(u, r - 1, s - i*r, m)
            u[i] = False
    m[(n, r, s)] = ans
    return m[(n, r, s)]

memo = {}
while True:
    try:
        n, s = map(int, input().split())
        used = [False for i in range(10)]
        ans = check(used, n, s, memo)
        print(ans)
    except:
        break
### BUGGY CODE ###

a, b, c, k = map(int, input().split())
a_num = a
b_num = b
c_num = c
ans = 0

for i in range(1, k+1):
    if a_num > 0:
        ans += 1
        a_num -= 1
    elif b_num > 0:
        b_num -= 1
    else:
        ans -= 1
        c_num -= 1
print(ans)

### FIXED CODE ###

a, b, c, k = map(int, input().split())
if a >= k:
    ans = k
elif a+b >= k:
    ans = a
else:
    ans = a - (k - a - b)
print(ans)
### BUGGY CODE ###

# C Green_Bin
n = int(input())
sl = []
ans = 0
for i in range(n):
    s = "".join(sorted(input()))
    for j in range(i):
        if (sl[j] == s):
            ans += 1
    sl.append(s)

print(ans)


### FIXED CODE ###

# C Green_Bin
n = int(input())
sl = []
ans = 0
for i in range(n):
    s = "".join(sorted(input()))
    sl.append(s)
sl.sort()
bi = ""
tmp = 0
for i in sl:
    if (bi == i):
        tmp += 1
    else:
        ans += (tmp+1)*(tmp)//2
        tmp = 0
    bi = i
ans += (tmp+1)*(tmp)//2

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

n, q = list(map(int, input().split()))
s = input().split()[0]
lr_list = []
lr_list = [list(map(int, input().split())) for _ in range(q)]

count_ac_list = [s[:i+1].count('AC') for i in range(n)]

count_list = [str(count_ac_list[r-1] - count_ac_list[l-1])
    if l > 1 else str(count_ac_list[r-1])
    for l, r in lr_list]

print('\n'.join(count_list))


### FIXED CODE ###

n, q = list(map(int, input().split()))
s = input().split()[0]
lr_list = [list(map(int, input().split())) for _ in range(q)]

count_ac_list = [0] * n
for i in range(n-1):
    # print('{}: {}'.format(i, s[i:i+2]))
    if s[i:i+2] == 'AC':
        count_ac_list[i+1] = count_ac_list[i] + 1
    else:
        count_ac_list[i+1] = count_ac_list[i]

count_list = [str(count_ac_list[r-1] - count_ac_list[l-1]) for l, r in lr_list]

print('\n'.join(count_list))
### BUGGY CODE ###

S = list(map(int, input()))
L = len(S)
mod = 2019
ans = 0
for i in range(L):
  a = 0
  j = i
  while j < L:
    a = (10 * a + S[j]) % mod
    if a == 0:
      ans += 1
    j += 1
print(ans)

### FIXED CODE ###

S = list(map(int, input()))
L = len(S)
mod = 2019
T = []
A = [0 for i in range(mod)]
t = 0
p = 1
for i in range(L-1, -1, -1):
  t = (t + S[i] * p) % mod
  A[t] += 1
  p = (p * 10) % mod
print(A[0] + sum([a * (a-1) // 2 for a in A]))
### BUGGY CODE ###

s = input()
q = int(input())
count = 1
while count < q+1:
    line = list(input())
    if line[0] == "2":
        if line[2] == "1":
            s = line[4] + s
        else:
            s = s + line[4]
    else:
        s = s[::-1]
    count += 1
print(s)

### FIXED CODE ###

s = input()
q = int(input())
list1 = []
list2 = []
flag = 1
for i in range(q):
    in_line = input().split()
    if in_line[0] == "1":
        flag *= -1
    else:
        if in_line[1] == "1":
            if flag == 1:
                list1.append(in_line[2])
            else:
                list2.append(in_line[2])
        else:
            if flag == 1:
                list2.append(in_line[2])
            else:
                list1.append(in_line[2])
if flag == 1:
    print("".join(list1[::-1]) + s + "".join(list2))
else:
    print("".join(list2[::-1]) + s[::-1] + "".join(list1))
### BUGGY CODE ###

N, D, A = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

ans = 0
for i in range(N):
    if XH[i][1] > 0:
        n_bomb = -(-XH[i][1]//A)
        ans += n_bomb
        j = i
        while j <= N-1 and XH[j][0] <= XH[i][0] + 2*D:
            XH[j][1] -= n_bomb * A
            j += 1

print(ans)

### FIXED CODE ###

# F - Silver Fox vs Monster

import bisect

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    # sum[0:i+1]
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    # add x to i
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, D, A = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

X = [XH[i][0] for i in range(N)]
X_right = [bisect.bisect_right(X, XH[i][0] + 2*D) for i in range(N)]

ans = 0
bomb_damage = Bit(N+1)
for i in range(N):
    damage = bomb_damage.sum(i+1)
    if XH[i][1] - damage > 0:
        n_bomb = -(-(XH[i][1] - damage)//A)
        ans += n_bomb
        bomb_damage.add(i+1, n_bomb * A)
        bomb_damage.add(X_right[i]+1, -n_bomb * A)

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

from math import log
def gcd(a,b):
    if a<b: a,b=b,a
    while b: a,b = b, a%b
    return a
a, b = map(int, input().split())
c = gcd(a, b)
ans = 1
i = 2
while c!=1:
    if c%i==0: ans+=1
    while c%i==0: c//=i
    i+=1
print(ans)

### FIXED CODE ###

def prefactor(x):
  ret = set()
  for i in range(2, int(x**0.5)+1):
    if x%i==0: ret.add(i)
    while x%i==0: x //= i
  if x>1: ret.add(x)
  return ret
    

a, b = map(int, input().split())
print(1+len(prefactor(a) & prefactor(b)))
### BUGGY CODE ###

S = list(input().strip())
N = len(S)

for i in range(1, N):
    if (S[i-1] == 'R') & (S[i] == 'L'):
        S[i-1], S[i] = 1, 1
        
for i in range(N):
    if S[i] == 'R':
        j = 1
        while S[i+j] == 'R':
            j += 1
        S[i+j+(j%2)] += 1
        S[i] = 0


for i in range(N-1, -1, -1):        
    if S[i] == 'L':
        j = 1
        while S[i-j] == 'L':
            j += 1
        S[i-j-(j%2)] += 1
        S[i] = 0


        
print(*S)        

### FIXED CODE ###

S = input() 
N = len(S)
S += 'R'

rnl = []
tmp = 'R'
cnt = 1
for i in range(1, N+1):
    if S[i] == tmp:
        cnt += 1
    else:
        rnl.append(cnt)
        tmp = S[i]
        cnt = 1

ans = [0] * N
i = 0
for j in range(len(rnl)):
    r = rnl[j]
    # R zone
    if j % 2 == 0:
        ans[i+r-1] += (r+1) // 2
        ans[i+r] += r // 2
        i += r
    # L zone
    else:
        ans[i] += (r+1) // 2
        ans[i-1] += r // 2
        i += r

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

n = int(input())
s = []
a = map(int,input().split())
for x in a:
    s.append(x)
    s = s[::-1]
print(*s)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if n % 2 == 0:
    a = a[::-2]+a[0::2]
else: a = a[::-2] +a[1::2]
print(*a,sep=" ")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush

N = int(input())
INF = float("inf")
costs = {n: INF for n in range(N)}
costs[0] = 0
graph = [{} for _ in range(N)]

unsearched = list(range(N))

for n in range(N):
    inp = tuple(map(int, input().split()))
    assert n == inp[0]
    for i in range(inp[1]):
        graph[n][inp[2*i+2]] = inp[2*i+3]

heap = [[0, 0]]
while len(unsearched) > 1:
    if len(heap):
        _, p = heappop(heap)
        unsearched.remove(p)
    heap = []
    for g in graph[p].keys():
        if g in unsearched:
            new_cost = costs[p] + graph[p][g]
            if new_cost < costs[g]:
                costs[g] = new_cost
            heappush(heap, [new_cost, g])
        else:
            pass

for n in range(N):
    print("{} {}".format(n, costs[n]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from heapq import heappop, heappush
def inpl(): return list(map(int, input().split()))
INF = float("inf")
N = int(input())
G = []
for _ in range(N):
    I = inpl()
    G.append(zip(*[I[3::2], I[2::2]]))

def dijkstra(G):
    C = [INF]*(N)
    C[0] = 0
    visited = [False] * (N)
    Q = [[0, 0]]

    while Q:
        c, u = heappop(Q)
        if C[u] < c:
            continue
        visited[u] = True
        for d, v in G[u]:
            if visited[v]:
                continue
            e = c + d
            if e < C[v]:
                C[v] = e
                heappush(Q, [e, v])
    return C

for i, c in enumerate(dijkstra(G)):
    print(i, c)
### BUGGY CODE ###

from itertools import combinations
n = int(input())
s = input()
ans = []
for i in combinations(s, 3):
    ans += [''.join(i)]
print(len(set(ans)))


### FIXED CODE ###

n = int(input())
s = list(input())
ans = 0

for i in range(0, 1000):
    count = 0
    val = list(str(i).zfill(3))
    k = val[count]
    for j in s:
        if j == k:
            count += 1
            if count <= 2:
                k = val[count]
            elif count == 3:
                ans += 1
                break
print(ans)
### BUGGY CODE ###

from collections import Counter
n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
count_a = Counter(a)

for i in range(1, n+1):
    point = k
    for key, value in count_a.items():
        if key != i:
            point -= value
    if point <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

#正解者以外のポイントを1減らすことと、全員のポイントを1減らしてから正解者のポイントだけ1増やすのは同じこと
from collections import Counter
n, k, q = map(int, input().split())
point = k - q
participant = [point] * n
answer = [int(input()) for _ in range(q)]
count_a = Counter(answer)


for key, value in count_a.items():
    participant[key-1] += value

for i in participant:
    if i > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from heapq import heappop, heappush


def solve():
    N, M = map(int, input().split())
    loadmap = [[] for _ in range(N + 1)]
    for _ in range(M):
        A, B = map(int, input().split())
        loadmap[A].append(B)
        loadmap[B].append(A)

    dbmap = [[float('inf'), -1] for _ in range(N + 1)]  # 部屋の深度, しるべ
    rooms = [[0, 1, 0]]  # [移動前の部屋, 移動後(現在)の部屋, 深度]
    while rooms:
        br, r, d = heappop(rooms)
        if d <= dbmap[r][0]:
            # update room data
            dbmap[r][0] = d
            dbmap[r][1] = br
            # add new room data
            for l in loadmap[r]:
                heappush(rooms, [r, l, d + 1])

    if min([db[1] for db in dbmap[1:]]) == -1:
        print('No')
    else:
        print('Yes')
        for db in dbmap[2:]:
            print(db[1])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

from heapq import heappop, heappush
from collections import deque


def solve():
    N, M = map(int, input().split())
    loadmap = [[] for _ in range(N + 1)]
    for _ in range(M):
        A, B = map(int, input().split())
        loadmap[A].append(B)
        loadmap[B].append(A)

    dbrmap = [[float('inf'), -1, 0] for _ in range(N + 1)]  # 部屋の深度, しるべ, 予約状態

    # rooms = [[0, 1, 0]]  # [移動前の部屋, 移動後(現在)の部屋, 深度]
    rooms = deque()
    rooms.append([0, 1, 0])
    dbrmap[1][2] = 1
    while rooms:
        # br, r, d = heappop(rooms)
        br, r, d = rooms.popleft()
        if d <= dbrmap[r][0]:
            # update room data
            dbrmap[r][0] = d
            dbrmap[r][1] = br
            # add new room data
            for load in loadmap[r]:
                # heappush(rooms, [r, l, d + 1])
                if dbrmap[load][2] == 0:
                    rooms.append([r, load, d + 1])
                    dbrmap[load][2] = 1

    if min([db[1] for db in dbrmap[1:]]) <= -1:
        print('No')
    else:
        print('Yes')
        for db in dbrmap[2:]:
            print(db[1])


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

K,S=map(int,input().split())
count=0
for i in range(K+1):
  for j in range(K+1):
    for k in range(K+1):
      if i+j+k==S:
        count+=1
        
print(count)

### FIXED CODE ###

K,S=map(int,input().split())
count=0
for i in range(K+1):
  for j in range(K+1):
    k = S-i-j
    if 0 <= k <= K:
        count+=1      
        
print(count)
### BUGGY CODE ###

N = int(input())
import fractions

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

ans_max = 0
for i in range(N):
    if i == 0:
        ans = 0
    else:
        ans = a[0]
    for j in range(1, N):
        if i == j:
            ans = fractions.gcd(ans, 0)
        else:
            ans = fractions.gcd(ans, a[j])
    ans_max = max(ans, ans_max)

print(ans_max)

### FIXED CODE ###

N = int(input())
import fractions

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

gcd_start = [0]
gcd_end = [0]

ans = a[0]
gcd_start.append(ans)
for i in range(1, N-1):
    ans = fractions.gcd(ans, a[i])
    gcd_start.append(ans)

ans = a[-1]
gcd_end.append(ans)
for i in range(-2, -N, -1):
    ans = fractions.gcd(ans, a[i])
    gcd_end.append(ans)

ans_max = 0
for i in range(N):
    ans = fractions.gcd(gcd_end[-i-1], gcd_start[i])
    ans_max = max(ans, ans_max)

print(ans_max)