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

import numpy as np

N = int(input())
A = np.sort(list(map(int,input().split())))[::-1]
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        a = A[i]
        b = A[j]
        C = A[j+1:]
        J = (C>a-b)
        if (np.any(J)):
            ans += np.size(C[J])

print(ans)

### FIXED CODE ###

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

#N=len(sticks)
sticks = sorted(sticks1, reverse=True)
#sticks.sort(reverse = True)
count = 0
jmax = N-2
kmax = N-1
i=0
while i<N-2:
    j= i+1
    while j<jmax+1:
        k=kmax
        while j<k:
            #sticks[i]>sticks[j]>sticks[k]
            if sticks[i]<sticks[j]+sticks[k]:
                count += k-j
                kmax = k
                break
            else:
                k -= 1
                continue
        jmax = kmax-1
        j += 1
    kmax = N-1
    jmax = N-2
    i += 1
      
print(count)
### BUGGY CODE ###

n = int(input())
lst = [int(i) for i in input().split()]

for i in range(n):
    lst[i] -= i+1

Min = min(lst)
Max = max(lst)

for b in range(Min,Max+1):
    scr = 0
    for i in range(n):
        scr += abs(lst[i] - b)
    if b == Min:
        Min_scr = scr
    elif scr < Min_scr:
        Min_scr = scr
print(Min_scr)

### FIXED CODE ###

n = int(input())
lst = [int(i) for i in input().split()]

for i in range(n): #Bi
    lst[i] -= i+1

lst.sort()
if n%2 == 0:
    k = n//2
    b = (lst[k] + lst[k-1])/2
else:
    k = (n-1)//2
    b = lst[k]

ans = 0
for i in range(n):
    ans += abs(lst[i] - b)

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

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

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X = readline()
    bit_count = X.count('1')
    X_int = int(X, 2)


    for i in range(N):
        # ビットの反転
        bit_count_n = bit_count
        X_rest = 0
        if X[i] == '0':
            bit_count_n += 1
            X_rest = X_int + pow(2, N - 1 - i)
        else:
            bit_count_n -= 1
            X_rest = X_int - pow(2, N - 1 - i)

        if X_rest == 0:
            print(0)
        else:
            popcount_X = X_rest % bit_count_n
            counter = 1
            while popcount_X != 0:
                popcount_X = popcount(popcount_X)
                counter += 1
            print(counter)






### FIXED CODE ###

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

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X = readline()
    bit_count = X.count('1')
    mod1 = int(X, 2) % (bit_count + 1)
    mod2 = int(X, 2) % (bit_count - 1) if (bit_count - 1) != 0 else 0

    for i in range(N):
        if X[i] == '0':
            X_rest = (mod1 + pow(2, N - 1 - i, bit_count + 1)) % (bit_count + 1)
        else:
            if bit_count - 1 != 0:
                X_rest = (mod2 - pow(2, N - 1 - i, bit_count - 1)) % (bit_count - 1)
            else:
                print(0)
                continue

        counter = 1
        while X_rest != 0:
            X_rest = popcount(X_rest)
            counter += 1
        print(counter)
### BUGGY CODE ###

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

def calc_expected_val(val):
    return (K+val)/2

def main():
    sum_K_list = []
    max_sum_K = 0
    max_expected_val = 0
    for i in range(N-K+1):
        sum_K = 0   
        for j in range(i, i+K):
            sum_K += P[j]
        sum_K_list.append(sum_K)

    max_sum_K = max(sum_K_list)
    max_expected_val = calc_expected_val(max_sum_K)    
    print(max_expected_val)

if __name__ == "__main__":
    main()
    

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int,input().split()))
ans = 0
cum = [0]
     
for i in range(len(p)):
    ex = (1 + p[i])/2
    p[i] = ex
        
for i in  range(len(p)):
    cum.append(p[i] + cum[i])
        
for i in range(K, N+1):
    ans  = max(ans, cum[i] - cum[i-K])
     
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = 1
for i in a:
    b = i * b
if b > 10 ** 18:
    print("-1")
else:
    print(b)


### FIXED CODE ###

def main():
	N = int(input())
	A = list(map(int, input().split()))
 
	if 0 in A:
		print(0)
		return
 
	prod = 1
	for a in A:
		prod *= a
		if prod > int(10**18):
			print(-1)
			return
 
	print(prod)
 
main()
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
B=[0]*62
mod=10**9+7

for i in range(n):
    a=bin(A[i])[2:]
    for j in range(len(a)):
        B[-j-1]+=int(a[-j-1])
ans=0
cnt=1
for b in range(len(B)):
    prd=B[-b-1]*(n-B[-b-1])
    ans+=prd*cnt%mod
    cnt*=2
    ans%=mod
    cnt%=mod
print(ans)

### FIXED CODE ###

#XORはビットごとに独立しているので各ビットで0*1の演算回数を数える
n=int(input())
A=list(map(int,input().split()))
B=[0]*62 #1の個数カウント
mod=10**9+7

for i in range(n):
    a=bin(A[i])
    for j in range(len(a)-2):
        if a[-j-1]=="1":
            B[-j-1]+=1

ans=0
cnt=1 #2の累乗管理
for b in range(len(B)):
    prd=B[-b-1]*(n-B[-b-1])
    ans+=prd*cnt%mod
    cnt*=2
    ans%=mod
    cnt%=mod
print(ans)
### BUGGY CODE ###

#import numpy as np
import functools
import operator
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as comb_with
#from itertools import permutations as perm


N = int(input())
#H1,M1,H2,M2,K= map(int,input().split())
A = list(map(int,input().split()))
#B = list(map(int,input().split()))
#S= str(input())
prod = functools.partial(functools.reduce, operator.mul)

#c=np.array(A)
p=prod(A)
if p<0:
    p=p*(-1)

if p>10**18:
    print(-1)
else:
    print(p)


### FIXED CODE ###

N = int(input())
#H1,M1,H2,M2,K= map(int,input().split())
A = list(map(int,input().split()))
#B = list(map(int,input().split()))
#S= str(input())
#prod = functools.partial(functools.reduce, operator.mul)
#c=np.array(A)
#p=np.prod(A)
c=1
if 0 in A:
    print(0)
    exit()
for i in A:
    c=c*i
    if c>10**18:
        print(-1)
        exit()
print(c)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
dic = {}
for i in a:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

for i in a:
    point = 0
    for j,k in dic.items():
        if j == i:
            point += (k-1)*(k-2)//2
        else:
            point += k*(k-1)//2
    print(point)

### FIXED CODE ###

from sys import stdin,setrecursionlimit
n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))
lin = [0]*(n+1)
for i in li:
    lin[i] += 1
liv = [0]*(n+1)
point = 0
for j,k in enumerate(lin):
    point += k*(k-1)//2
    liv[j] += k*(k-1)//2
for i in li:
    print(point-liv[i]+(lin[i]-1)*(lin[i]-2)//2)
### BUGGY CODE ###

s = input()
t = input()
n, m = len(s), len(t)
dp = [[""]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + s[i]
    else:
      if len(dp[i+1][j]) >= len(dp[i][j+1]):
        dp[i+1][j+1] = dp[i+1][j]
      else:
        dp[i+1][j+1] = dp[i][j+1]
print(dp[n][m])

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = input().rstrip()
t = input().rstrip()
ls = len(s)
lt = len(t)
dp = [[0]*(lt+1) for _ in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
ans = ""
while ls > 0 and lt > 0:
  if dp[ls][lt] == dp[ls-1][lt]:
    ls -= 1
  elif dp[ls][lt] == dp[ls][lt-1]:
    lt -= 1
  else:
    ans = s[ls-1] + ans
    ls -= 1
    lt -= 1
print(ans)
### BUGGY CODE ###

def main():
  n=int(input())
  s=list(input())
  q_=int(input())
  q=[input().split() for _ in range(q_)]
  """
  n=500000
  s=list('abcdfghijk'*(n//10))
  q_=200
  q=[]
  n2a = lambda c: chr(c%26+1+64).lower()
  for i in range(q_):
    if True:
      q.append(['1',str(i*11),n2a(i)])
    else:
      q.append(['2',str(i),str(i*11)])
  """
  import numpy as np
  a2n = lambda c: ord(c) - ord('a')
  d=[[0]*26]
  di=[0]*26
  for si in s:
    di[a2n(si)]+=1
    d.append(di.copy())
  d=np.array(d)
  for qi in q:
    if qi[0]=='1':
      i=int(qi[1])
      c=a2n(qi[2])
      si=a2n(s[i-1])
      d[i:,c]+=1
      d[i:,si]-=1
      s[i-1]=qi[2]
    else:
      l,r=int(qi[1]),int(qi[2])
      ld=d[l-1]
      rd=d[r]
      print(len([i for i in range(26) if rd[i]-ld[i]>0]))
if __name__=='__main__':
  main()
  

### FIXED CODE ###

def main():
  n=int(input())
  s=list(input())
  q_=int(input())
  q=[input().split() for _ in range(q_)]
  class BIT:
    def __init__(self, n):
      self.n = n
      self.data = [0]*(n+1)
      self.el = [0]*(n+1)
    def sum(self, i):
      s = 0
      while i > 0:
        s += self.data[i]
        i -= i & -i
      return s
    def add(self, i, x):
      # assert i > 0
      self.el[i] += x
      while i <= self.n:
        self.data[i] += x
        i += i & -i
    def get(self, i, j=None):
      if j is None:
        return self.el[i]
      return self.sum(j) - self.sum(i)

  a2n = lambda c: ord(c) - ord('a')
  d=[BIT(n) for _ in range(26)]
  di=[0]*26
  for i in range(1,n+1):
    d[a2n(s[i-1])].add(i,1)
  for qi in q:
    if qi[0]=='1':
      i=int(qi[1])
      c=a2n(qi[2])
      si=a2n(s[i-1])
      d[c].add(i,1)
      d[si].add(i,-1)
      s[i-1]=qi[2]
    else:
      ans=0
      l,r=int(qi[1]),int(qi[2])
      for i in range(26):
        ls=d[i].sum(l-1)
        rs=d[i].sum(r)
        ans+=1 if rs-ls>0 else 0
      print(ans)
if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())
### BUGGY CODE ###

K, S = list(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 = list(map(int,input().split()))
count = 0
for i in range(K+1):
  for j in range(K+1):
    if 0<=S-i-j and S-i-j<=K:
        count += 1
print(count)
### BUGGY CODE ###

from collections import deque
n,k = map(int,input().split())
l = list(map(int,input().split()))
product = 1
for i in range(k):
    product *= l[i]

que = deque(l[:k])
for i in range(n-k):
    previous = product
    product //= que.popleft()
    product *= l[k+i]
    if product <= previous:
        print('No')
    else:
        print('Yes')
    que.append(l[k+i])

### FIXED CODE ###

from collections import deque
n,k = map(int,input().split())
l = list(map(int,input().split()))

que = deque(l[:k])
for i in range(n-k):
    p = que.popleft()
    que.append(l[k+i])
    if p < l[k+i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

def main():
    n = int(input())
    h = np.array(input().split(), dtype='int')

    ans = 0

    for i in range(n - 1):
        times_move = 0
        for j in range(n - i - 1):
            if h[i + j] < h[i + j + 1]:
                break
            else:
                times_move += 1
        if times_move > ans:
            ans = times_move
        if n - i - 1 <= ans:
            break

    print(ans)


main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

def main():
    n = int(input())
    h = np.array(input().split(), dtype='int')

    ans = 0
    i = 0

    while i < n:
        times_move = 0
        for j in range(n - i - 1):
            if h[i + j] < h[i + j + 1]:
                break
            else:
                times_move += 1
        if times_move > ans:
            ans = times_move
        if n - i - 1 <= ans:
            break
        i += times_move + 1

    print(ans)


main()
### BUGGY CODE ###

N,P=[int(s) for s in input().split()]
DP=[[0 for _ in range(i+1)] for i in range(N)]
ls=[int(s)%P for s in list(input())]

count=[[0 for _ in range(P)] for _ in range(N)]


for j in range(N):
  count[j][ls[j]]+=1

for i in range(1,N):
  a=ls[i]
  for k in range(P):
    if count[i-1][k]!=0:
      count[i][(10*k+a)%P]+=count[i-1][k]
  
ans=0
for j in range(N):
  ans+=count[j][0]
print(ans)

### FIXED CODE ###

N,P=[int(s) for s in input().split()]
S=list(input())
if P!=2 and P!=5:
  ls=[0 for _ in range(N)]
  mod=[0 for _ in range(P)]
  d=10
  ls[0]=int(S[-1])%P
  mod[ls[0]]+=1
  for i in range(1,N):
    ls[i]=(ls[i-1]+d*int(S[-1-i]))%P
    d=(d*10)%P
    mod[ls[i]]+=1
  #print(ls)
  #print(mod)  
  ans=mod[0]
  for i in range(N):
    m=ls[i]
    mod[ls[i]]-=1
    ans+=mod[ls[i]]
else:
  ans=0
  for i in range(N):
    if int(S[i])%P==0:
      ans+=i+1
print(ans)
### BUGGY CODE ###

N = int(input())
p = list(map(int, input().split()))
cnt = 0
i = 0
while i < N:
    if i + 1 == p[i]:
        c = 1
        for j in range(i + 1, N):
            if j+1 != p[j]:
                i = j
                break
            else:
                c += 1
        i = j
        cnt += (c+1)//2
    i += 1

print(cnt)
        

### FIXED CODE ###

N = int(input())
p = list(map(int, input().split()))
cnt = 0
i = 0
while i < N:
    if i + 1 == p[i]:
        c = 1
        j = i+1
        while j < N:
            if j+1 != p[j]:
                i = j
                break
            else:
                c += 1
            j += 1
        else:
            i = j
        cnt += (c+1)//2
    i += 1

print(cnt)
### BUGGY CODE ###

import itertools



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

L.sort()

ans = 0

for c_i in range(2, N):
    a_i = 0
    while L[c_i] >= L[a_i] + L[c_i - 1] and a_i < c_i - 1:
        a_i += 1
    
    ans += sum([1 if L[comb[0]] + L[comb[1]] > L[c_i] else 0 for comb in itertools.combinations(range(a_i, c_i), 2)])

print(ans)

### FIXED CODE ###

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

L.sort()

ans = 0

for a in range(N - 2):
    c = a + 1
    for b in range(a + 1, N - 1):
        while c < N - 1 and L[c + 1] < L[a] + L[b]:
            c += 1
        ans += c - b

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


import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
K = int(input())


ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
           

                ans += gcd(i+1,j+1,k+1)
            #1-Kまで
print(ans)




### FIXED CODE ###

import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
K = int(input())
 
 
ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
           
 
                ans += gcd(i+1,j+1,k+1)
            #1-Kまで
print(ans)
### BUGGY CODE ###

import bisect
n = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
ans = 0
for i in A:
  for j in B[bisect.bisect_right(B, i):]:
    ans += n - bisect.bisect_right(C, j)
print(ans)

### FIXED CODE ###

import bisect
from itertools import accumulate
n = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
ans = 0
b_to_c = [0]*n
for i in range(n):
  b_to_c[i] = n - bisect.bisect_right(C, B[i])
Q = list(accumulate(b_to_c[::-1]))[::-1]
  
for i in A:
  t = bisect.bisect_right(B, i)
  if t < n:
    ans += Q[t]
print(ans)
### BUGGY CODE ###

h, w, a, b = map(int, input().split(' '))

MOD = 10**9 + 7
MAX = 10**6 + 5


def mod(a, b):
    r = 1
    while b:
        if b & 1:
            r = (r * a) % MOD
        a = (a * a) % MOD
        b >>= 1
    return r


f = [0]*MAX
invf = [0]*MAX


def ncr(n, r):
    if r == 0 or r == n:
        return 1
    return (((f[n] * invf[n-r]) % MOD) * invf[r]) % MOD


f[0] = 1
for i in range(1, MAX):
    f[i] = (f[i-1] * i) % MOD
    invf[i] = mod(f[i], MOD-2)
r = 0
for i in range(b, w):
    y1 = h - a - 1
    x1 = i
    y2 = a - 1
    x2 = w - i - 1
    p = (ncr(x1 + y1, x1) * ncr(x2 + y2, x2)) % MOD
    r = (r + p) % MOD

print(r)


### FIXED CODE ###

from array import *
import time
h, w, a, b = map(int, input().split(' '))
MOD = 10**9 + 7
MAX = max(h+w-a-1, a+w)


def modpow(a, b):
    res = 1
    while b:
        if (b & 1):
            res = (res * a) % MOD
        a = (a * a) % MOD
        b >>= 1
    return res


def nCr(n, r):
    if r == 0 or n == r:
        return 1
    return (((f[n] * ivf[n-r]) % MOD) * ivf[r]) % MOD


f = [1] * MAX
f = array('q', f)
ivf = [0] * MAX
ivf = array('q', ivf)
for i in range(1, MAX):
    f[i] = (f[i-1] * i) % MOD
    ivf[i] = modpow(f[i], MOD-2)
r = 0
for i in range(b, w):
    y1 = h - a - 1
    x1 = i
    y2 = a - 1
    x2 = w - i - 1
    p = (nCr(x1 + y1, x1) * nCr(x2 + y2, x2)) % MOD
    r = (r + p) % MOD
print(int(r))
### BUGGY CODE ###

X,Y,Z,K = (int(num) for num in input().split())
a = [int(num) for num in input().split()]
b = [int(num) for num in input().split()]
c = [int(num) for num in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

l = [(0,0,0,a[0]+b[0]+c[0])]
unvisited = [[[True for i in range(X)] for j in range(Y)] for k in range(Z)]
unvisited[0][0][0] = False
for i in range(K):
    xt,yt,zt,pt = l.pop(0)
    print(pt)
    list_dx = [1,0,0]
    list_dy = [0,1,0]
    list_dz = [0,0,1]
    for j in range(3):
        dx = list_dx[j]
        dy = list_dy[j]
        dz = list_dz[j]
        if xt+dx<X and yt+dy<Y and zt+dz<Z and unvisited[xt+dx][yt+dy][zt+dz]:
            l.append((xt+dx,yt+dy,zt+dz,a[xt+dx]+b[yt+dy]+c[zt+dz]))
            l.sort(key=lambda x:x[3], reverse=True)
            unvisited[xt+dx][yt+dy][zt+dz] = False

### FIXED CODE ###

X,Y,Z,K = (int(num) for num in input().split())
a = [int(num) for num in input().split()]
b = [int(num) for num in input().split()]
c = [int(num) for num in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

l = []
for i in range(X):
    if i+1 > K:
        break
    
    for j in range(Y):
        if (i+1) * (j+1) > K:
            break
        
        for k in range(Z):
            if (i+1) * (j+1) * (k+1) > K:
                break
            
            l.append(a[i]+b[j]+c[k])
            
            
l.sort(reverse=True)
for i in range(K):
    print(l[i])
### BUGGY CODE ###

from collections import defaultdict
from operator import add, mul
import sys
sys.setrecursionlimit(1000000)


d = defaultdict(list)
N, M = map(int, input().split())
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

q = [1]
parents = [-1]*(N+1)
dp = defaultdict(lambda: defaultdict(int))
ans = [0]*(N+1)
merge = lambda x,y:mul(x, y)
add_root = lambda x:x#+1
e = 1


def dfs1(s):
    v = e
    for t in d[s]:
        if t == parents[s]:
            continue
        parents[t] = s
        v = merge(v, dfs1(t)+1)
    dp[parents[s]][s] = add_root(v)
    return add_root(v)


def dfs2(s):
    q = [(s, e)]
    while q:
        s, dp_p = q.pop()
        par = parents[s]
        for t in d[s]:
            if t == par:
                dp[s][t] = dp_p

        size = len(d[s])
        ac_l = [e] * (size+1)
        ac_r = [e] * (size+1)
        for i, t in enumerate(d[s]):
            ac_l[i+1] = merge(ac_l[i], dp[s][t]+1)%M
        for i, t in enumerate(d[s][::-1]):
            ac_r[size-i-1] = merge(ac_r[size-i], dp[s][t]+1)%M
        ans[s] = add_root(ac_l[size])
        for i, t in enumerate(d[s]):
            if t == par:
                continue
            q.append((t, add_root(merge(ac_l[i], ac_r[i+1])%M)))


dfs1(1)
dfs2(1)
for i in range(1, N+1):
    print(ans[i])


### FIXED CODE ###

from collections import defaultdict
from operator import add, mul
import sys
sys.setrecursionlimit(1000000)


d = defaultdict(list)
N, M = map(int, input().split())
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

q = [1]
parents = [-1]*(N+1)
dp = defaultdict(lambda: defaultdict(int))
ans = [0]*(N+1)
merge = lambda x,y:mul(x, y)
add_root = lambda x:x#+1
e = 1


def dfs1(s):
    l = []
    q = [1]
    while q:
        s = q.pop()
        l.append(s)
        for t in d[s]:
            if t==parents[s]:
                continue
            parents[t] = s
            q.append(t)

    for s in l[::-1]:
        v = e
        for t in d[s]:
            if t == parents[s]:
                continue
            v = merge(v, dp[s][t]+1)
        dp[parents[s]][s] = add_root(v)
    # return add_root(v)


def dfs2(s):
    q = [(s, e)]
    while q:
        s, dp_p = q.pop()
        par = parents[s]
        for t in d[s]:
            if t == par:
                dp[s][t] = dp_p

        size = len(d[s])
        ac_l = [e] * (size+1)
        ac_r = [e] * (size+1)
        for i, t in enumerate(d[s]):
            ac_l[i+1] = merge(ac_l[i], dp[s][t]+1)%M
        for i, t in enumerate(d[s][::-1]):
            ac_r[size-i-1] = merge(ac_r[size-i], dp[s][t]+1)%M
        ans[s] = add_root(ac_l[size])
        for i, t in enumerate(d[s]):
            if t == par:
                continue
            q.append((t, add_root(merge(ac_l[i], ac_r[i+1])%M)))


dfs1(1)
dfs2(1)
for i in range(1, N+1):
    print(ans[i])
### BUGGY CODE ###

a, b, n = map(int, input().split())

if b == 1:
    r = [0]
else:
    i = 0
    r = []
    while b*i-1 <= n:
        r.append(int((a*(b*i-1))/b)-a*int((b*i-1)/b))
print(max(r))

### FIXED CODE ###

a, b, n = map(int, input().split())

if b == 1:
    r = [0]
else:
    i = 0
    r = [int((a*n)/b)-a*int(n/b)]
    while b*i-1 <= n:
        r.append(int((a*(b*i-1))/b)-a*int((b*i-1)/b))
        i += 1
print(max(r))
### BUGGY CODE ###

n = int(input())
count = 0
for l in range(1, n+1):
  for i in range(1,13):
    for j in range(1, 13):
      for k in range(1, 13):
        if (i+j+k)**2-(i*j+j*k+i*k) == l:
          count +=1
  print(count)
  count = 0    

### FIXED CODE ###

n = int(input())
count = 0
a = [0]*(10**5)
for i in range(1, 100):
  for j in range(1, 100):
    for k in range(1, 100):
      a[(i+j+k)**2-(i*j+j*k+i*k)] += 1


for i in range(n):
  print(a[i+1])
### BUGGY CODE ###

from heapq import heappush, heappop

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

neighbor = [[] for _ in range(n+1)]

for i in range(m):
    A, B = map(int, input().split())
    neighbor[A].append(B)
    neighbor[B].append(A)

h = []

heappush(h, (0, 1, 0))

ans = [0] * (n+1)
while h:
    step, cur, prev = heappop(h)
    if ans[cur] != 0:
        continue

    ans[cur] = prev

    for i in neighbor[cur]:
        heappush(h, (step+1, i, cur))

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


### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.buffer.readline

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

neighbor = [[] for _ in range(n+1)]

for i in range(m):
    A, B = map(int, input().split())
    neighbor[A].append(B)
    neighbor[B].append(A)

h = []

heappush(h, (0, 1, 0))

ans = [0] * (n+1)
while h:
    step, cur, prev = heappop(h)

    for i in neighbor[cur]:
        if ans[i] == 0:
            ans[i] = cur
            heappush(h, (step+1, i, cur))

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