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

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    import itertools
    T = list(itertools.accumulate(A))

    answer = pow(10, 10)
    for i in range(1, N-2):
        for a in range(i):
            for b in range(i+1, N-1):
                P = T[a]
                Q = T[i] - T[a]
                R = T[b] - T[i]
                S = T[-1] - T[b]
                temp = max(P, Q, R, S) - min(P, Q, R, S)
                answer = min(answer, temp)
        
    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()


### FIXED CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    import itertools
    import math
    B = list(itertools.accumulate(A))

    def f(a, i):
        return abs(B[i]-B[a]-B[a])
    def g(b, i):
        return abs(B[-1]-B[b]- (B[b]- B[i]))
    answer = pow(10, 10)
    for i in range(1, N-2):
        left1 = 0
        right1 = i
        while left1 + 2 < right1:
            c1 = left1 + (right1 - left1)//3
            c2 = right1 - (right1 - left1)//3
            if f(c1, i) > f(c2, i):#条件が満たされる:
                left1 = c1
            else:
                right1 = c2
        left2 = i
        right2 = N-1
        while left2 + 2 < right2:
            c3 = left2 + (right2 - left2)//3
            c4 = right2 - (right2 - left2)//3
            if g(c3, i) > g(c4, i):#条件が満たされる:
                left2 = c3
            else:
                right2 = c4
        p = sorted([(f(j, i), j) for j in range(left1, right1+1)])[0][1]
        q = sorted([(g(j, i), j) for j in range(left2, right2+1)])[0][1]
        m = min(B[p], B[i]-B[p], B[q]-B[i], B[-1]-B[q])
        M = max(B[p], B[i]-B[p], B[q]-B[i], B[-1]-B[q])
        answer = min(answer, M-m)

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()
### BUGGY CODE ###

a, b, x = map(int, input().split())
count = 0
for i in range(a, b+1):
    if i%x == 0:
        count += 1
print(count)

### FIXED CODE ###

a, b, x = map(int, input().split())
print(b//x - (a-1)//x)
### BUGGY CODE ###

import copy
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]
xh = sorted(xh, key=lambda x:(x[0]))
if d == 0:
    di = 0
else:
    di = 1 + 2*d
cnt = 0
while xh:
    c = xh.pop(0)
    cx, ch = c[0], c[1]
    if ch <= 0:
        continue
    if ch % a == 0:
        cn = ch // a
    else:
        cn = 1 + ch // a
    cnt += copy.deepcopy(cn)
    for nx in range(cx+1, cx+di+1):
        for i in range(len(xh)):
            if xh[i][0] == nx:
                xh[i][1] -= a * cn
print(cnt)

### FIXED CODE ###

from collections import deque
import sys

input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

xh = sorted(xh, key=lambda x:(x[0]))
q = deque()
ca = 0
cnt = 0
for i in range(n):
    cx, ch = xh[i][0], xh[i][1]
    
    while q and q[0][0] < cx:
        qx, qa = q.popleft()
        ca -= qa
    
    if ch - ca <= 0:
        continue
    
    cn = (ch - ca + a - 1) // a
    cnt += cn
    ca += cn * a
    q.append([cx+2*d, cn*a])
    
print(cnt)
### BUGGY CODE ###

import fractions
#a, b = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])

c = 0
for i in range(n):
    b = ans // a[i]
    c += b
    c %= mod

print(c)

### FIXED CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
 
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
 
c = 0
for i in range(n):
    b = ans // a[i]
    c += b
 
print(c % mod)
### BUGGY CODE ###

l=input()
dp=[[0,0] for _ in range(len(l))]
if l[-1]=='1':
  dp[-1][0]=1
  dp[-1][1]=2
else:
  dp[-1][0]=1
  dp[-1][1]=0
for i in range(len(l)-2,-1,-1):
  if l[i]=='0':
    dp[i][0]=dp[i+1][0]+dp[i+1][1]
    dp[i][1]=0
  else:
    dp[i][0]=(3**(len(l)-i-1))%(10**9+7)
    dp[i][1]=(2*(dp[i+1][0]+dp[i+1][1]))%(10**9+7)
print((dp[0][0]+dp[0][1])%(10**9+7))

### FIXED CODE ###

def qpow(b,t,m):
  f=format(t,'b')[::-1]
  arr=[b]
  tmp=b
  for i in range(1,len(f)):
    tmp=(tmp**2)%m
    arr.append(tmp)
  ans=1
  for i in range(len(f)):
    if f[i]=='1':
      ans=(ans*arr[i])%m
  return ans    

l=input()
dp=[[0,0] for _ in range(len(l))]
if l[-1]=='1':
  dp[-1][0]=1
  dp[-1][1]=2
else:
  dp[-1][0]=1
  dp[-1][1]=0
for i in range(len(l)-2,-1,-1):
  if l[i]=='0':
    dp[i][0]=dp[i+1][0]+dp[i+1][1]
    dp[i][1]=0
  else:
    dp[i][0]=qpow(3,len(l)-i-1,10**9+7)
    dp[i][1]=(2*(dp[i+1][0]+dp[i+1][1]))%(10**9+7)
print((dp[0][0]+dp[0][1])%(10**9+7))
### BUGGY CODE ###

from collections import deque
N,Q = map(int,input().split())
tree = {}
px = []
counter = [0 for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = [b]
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = [a]
for _ in range(Q):
    ip,ix = map(int,input().split())
    px.append([ip,ix])


oya = deque([1])

while oya:
    oyai = oya.popleft()
    for ko in tree[oyai]:
        tree[ko].remove(oyai)
        oya.append(ko)


for pi,xi in px:
    oya = deque([pi])
    
    while oya:
        oyai = oya.popleft()
        counter[oyai-1] +=xi
        for ko in tree[oyai]:
            oya.append(ko)  
[print(i,end=" ") for i in counter]


### FIXED CODE ###

# coding: utf-8
# Your code here!
from collections import deque
N,Q = map(int,input().split())
tree = {}
px = []
counter = [0 for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = [b]
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = [a]
for _ in range(Q):
    ip,ix = map(int,input().split())
    counter[ip-1] += ix


oya = deque([1])

while oya:
    oyai = oya.popleft()
    for ko in tree[oyai]:
        tree[ko].remove(oyai)
        counter[ko-1] += counter[oyai-1]
        oya.append(ko)




print(' '.join(map(str,counter)))
### BUGGY CODE ###

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

print(*b,sep=' ')


### FIXED CODE ###

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

b = [0] * n

if n % 2 == 0 :
    c = n//2 - 1
else :
    c = n // 2

b[c] = a[0]

for i in range(1,n) :
    if i % 2 == 1 :
        b[c + i] = a[i]
        c += i
    else :
        b[c - i] = a[i]
        c -= i

if c != 0 :
    b.reverse()
    print(*b,sep=" ")
else :
    print(*b,sep=" ")
### BUGGY CODE ###

s = input()

ans = 0
mods = {0: 1} # 0 % n = 0
for i in range(1, len(s)+1):
    x = int(s[len(s)-i:])
    # print(x)
    a = x%2019
    if a in mods.keys():
        mods[a] += 1
    else:
        mods[a] = 1
# print(mods)
for k in mods.keys():
    counts = mods[k]
    ans += counts // 2
print(ans)

### FIXED CODE ###

from collections import Counter
s = input()

ans = 0
mods = [0]
s = [int(a) for a in s[::-1]]
x = 0
for i in range(len(s)):
    x += s[i] * pow(10, i, 2019)
    mods.append(x%2019)

mods = Counter(mods)

for k in mods.keys():
    counts = mods[k]
    ans += counts * (counts-1) // 2
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):

        a1 = a_lst[i]
        a2 = a_lst[j]
        ans += (a1 % (10 ** 9 + 7)) * (a2 % (10 ** 9 + 7))
        ans %= (10 ** 9 + 7)

print(ans)

### FIXED CODE ###

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

a_lst.reverse()
tmp = a_lst[0]
lst = []
for i in range(1, n):
    lst.append(tmp)
    tmp += a_lst[i]
    tmp %= (10 ** 9 + 7)
lst.reverse()
a_lst.reverse()

ans = 0
for i in range(n - 1):
    ans += (a_lst[i] * lst[i]) % (10 ** 9 + 7)
ans %= (10 ** 9 + 7)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N-1):
    I = A[i]
    for j in range(i + A[i], N):
        if abs(i - j) == A[i] + A[j]:
            ans += 1
print(ans)

### FIXED CODE ###

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

Ai = dict()
ans = 0
for i, v in enumerate(A):
    ai = i + v
    if ai in Ai:
        Ai[ai].append(i)
    else:
        Ai[ai] = [i]
for i, v in enumerate(A):
    aj = i - v
    if aj in Ai:
        ans += len(Ai[aj])
print(ans)
### BUGGY CODE ###

A,B,C = map(int,input().split())
can = min(A+B,C)
eat = 0
for i in range(can):
    C -= 1
    eat += 1
    if A > 0:
        A -= 1
    else:
        eat += 1
        B -= 1

if C > 0:
    eat += 1

print(eat+B)

### FIXED CODE ###

A,B,C = map(int,input().split())
can = min(A+B,C)
eat = 0
C -= can
eat += can*2-A
B = A+B -can

if C > 0:
    eat += 1

print(eat+B)
### BUGGY CODE ###

if __name__ == "__main__":
    N = int(input())
    nmin = 10**12
    maxI = max(2, N//2)
    for n in range(1, maxI):
        if N % n == 0:
            nmin = min(nmin, n + N//n - 2)

    print(nmin)

### FIXED CODE ###

import math

if __name__ == "__main__":
    N = int(input())
    nsqrt = math.sqrt(N)
    for i in range(int(nsqrt), 0, -1):
        if N % i == 0:
            print(i + N//i - 2)
            exit()
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
ans = 0
c = collections.Counter(A)
for k in range(N):
    buf = A[k]
    ans = 0
    A[k] = 0
    c = collections.Counter(A)
    if (max(c.values())==1):
        print(0)
        A[k] = buf
        continue
    for l in c.values():
        ans = ans + l*(l-1)/2
    print(int(ans))
    A[k] = buf


### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
ans = 0
c = collections.Counter(A)
for l in c.values():
    ans = ans + l*(l-1)/2
for k in A:
    print(int(ans-(c[k]-1)))
### BUGGY CODE ###

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

maxleft = [0] * (N+2)
maxright = [0] * (N+2)

for i in range(N):
    maxleft[i+1] = max(A[0:i+1])
    maxright[i+1] = max(A[i:])

for i in range(N):
    print(max(maxleft[i], maxright[2+i]))


### FIXED CODE ###

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

maxleft = [0] * (N+2)
maxright = [0] * (N+2)

for i in range(N):
    maxleft[i+1] = max(maxleft[i],A[i])
    maxright[N-i] = max(maxright[N-i+1],A[N-i-1])

for i in range(N):
    print(max(maxleft[i], maxright[2+i]))
### BUGGY CODE ###

# ABC073 C - Write and Erase
# 2019/10/28

def main():
    N, *A = map(int, open(0).read().split())
#     print(N, A)
    set_A = list(set(A))
    list_count = [A.count(i)%2 for i in set_A]
#     print(list_count)
    print(sum(list_count))
    
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter

def main():
    N, *A = map(int, open(0).read().split())
#     print(N, A)
    c = Counter(A)
#     print(c)

    print(sum(v & 1 for v in c.values()))

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

n = int(input())
s = []
for i in range(n):
  s.append(''.join(sorted(input())))
a = []

l = len(s)
while l > 0:
  i = s[0]
  s = [ss for ss in s if ss != i]
  ll = len(s)
  a.append(l-ll)
  l = ll

ans = 0
for i in range(len(a)):
  ans += a[i]*(a[i]-1)//2
print(ans)

### FIXED CODE ###

n = int(input())
s = ['']*n
for i in range(n):
  s[i] = (''.join(sorted(input())))
s.sort()

i=0
c=1
ans = 0
while i < n-1:
  while i+c < n and s[i] == s[i+c]:
    c += 1
  else:
    ans += c*(c-1)//2
    i += c
    c = 1

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

N, K = map(int, input().split()) # 横に2個
L = [list(map(int, input().split())) for _ in range(N-1)]

mod = 10**9+7

neardic = {}
for p in range(1, N+1):
    near = []
    for l in L:
        if p in l:
            other = set(l) - {p}
            near.append(list(other)[0])
    neardic[p] = near


def color(p=1, state=[1], prob=K, checked=[]):
    nears = neardic[p]
    checked.append(p)
    unchecked_nears = set(nears) - set(checked)
    A = len(unchecked_nears)
    if A == 0:
        return prob
    if len(state) == 1:
        nextprobmax = K-1
    else:
        nextprobmax = K-2
    for i, near in enumerate(unchecked_nears):
        prob = prob * (nextprobmax - i) % mod
        nowstate = state[:]
        nowstate.append(near)
        prob = color(near, nowstate, prob, checked)
    return prob

print(color())




### FIXED CODE ###

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

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

checked = [False]*N
C = [None]*N
checked[0] = True

def dfs(p, c1, c2, depth):
    C[p] = c1 + c2
    d = 0
    for np in graph[p]:
        if not checked[np]:
            checked[np] = True
            d += 1
            g = 1 if depth > 0 else 0
            dfs(np, d, g, depth+1)
        

dfs(0, 0, 0, 0)
#print(C)

mod = 10**9+7
ans = 1
for n in range(N):
    ans = ans * (K-C[n]) % mod

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

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
for i in range(M):
  B,C=map(int,input().split())
  for j in range(B):
    if A[j]<C:
      A[j]=C
  A.sort()
print(sum(A))

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

BC=[list(map(int,input().split())) for _ in range(M)]
BC.sort(reverse=True,key=lambda x:x[1])

D=[]
for i in range(M):
  for j in range(BC[i][0]):
    D.append(BC[i][1])
    if len(D)==N:
      break
  if len(D)==N:
    break

for i in range(len(D)):
  if D[i]>A[i]:
    A[i]=D[i]
  else:
    break
print(sum(A))
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
score = 1
for i in a[:k]:
    score *= i


for num, i in enumerate(range(k, n)):
    k_i = score * a[i] / a[num]
    if score < k_i:
        print('Yes')
    else:
        print('No')

    score = k_i


### FIXED CODE ###

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

for num, i in enumerate(range(k, n)):
    if a[num] < a[i]:
        print('Yes')
    else:
        print("No")
### BUGGY CODE ###

# python3だとTLE,pypy3だとAC

def main():
    N = int(input())
    p = tuple(map(float, input().split()))
    dp = [[0.0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0
    for i in range(1, N+1):
        for j in range(0, N + 1):
            h = p[i - 1]
            t = 1-h
            dp[i][j] = dp[i - 1][j] * t + dp[i - 1][j - 1] * h
    print(sum(dp[N][N//2+1:]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    p_mul = 1
    dp[0][0] = 1
    for i in range(1, N + 1):
        p_mul *= (1-p[i-1])
        dp[i][0] = p_mul
    for i in range(1, N+1):
        for j in range(1, N+1):
            dp[i][j] = dp[i - 1][j] * \
                (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
    print(sum(dp[N][N//2+1:]))


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

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

set_A = set(A)
count_A = A.count(max(A))
for a in A:
    if a == max(A) and count_A == 1:
        print(sorted(set(set_A))[-2])
    else:
        print(max(A))

### FIXED CODE ###

def main():
    N = int(input())
    A = [0] * N
    for i in range(N):
        A[i] = int(input())

    set_A = set(A)
    max_A = max(A)
    count_A = A.count(max_A)
    for a in A:
        if a == max_A and count_A == 1:
            print(sorted(set_A)[-2])
        else:
            print(max_A)

main()
### BUGGY CODE ###

import heapq

class Dijkstra:
    def __init__(self,s,n,e,cost):
        #s:始点 n:頂点数,　e:辺の数, cost[u][v] : uからvのコスト(存在しないときはinf)
        self.s = s
        self.n = n
        self.e = e
        self.cost = cost


    def execute(self):

        dist = [float("inf") for _ in range(self.n)]
        prev = [float("inf") for _ in range(self.n)]

        dist[self.s] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.s))
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest in range(self.n):
                cost_ = cost[src][dest]
                if dist[dest] > dist[src] + cost_:
                    dist[dest] = dist[src] + cost_
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src

        return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

n = int(input())
cost = [[float('inf') for i in range(n)] for j in range(n)]

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

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

d = Dijkstra(k-1,n,n-1,cost).execute()


ans = [0]*q

for i in range(q):
    x, y = map(int, input().split())
    ans[i] = d[x-1]+d[y-1]

print(*ans, sep='\n')



### FIXED CODE ###

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

n = int(input())
from collections import defaultdict
abc = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b,c in abc:
    a,b = a-1,b-1
    es[a].append((b,c))
    es[b].append((a,c))

q, k = map(int, input().split())
xy = [tuple(map(int,input().split())) for i in range(q)]

dist = [-1]*n

def dfs(v=0,parent=-1,d=0):
    for next_v,dd in es[v]:
        if dist[next_v] == -1:
            dist[next_v] = d + dd
            dfs(next_v,v,dist[next_v])

dist[k-1] =0
dfs(k-1,-1,0)
ans=[]
for x,y in xy:
    x,y=x-1,y-1
    ans.append(dist[x]+dist[y])

print(*ans,sep='\n')
### BUGGY CODE ###

n, m = map(int, input().split())
from collections import defaultdict as dd
from bisect import insort
PY = dd(lambda:[0])
IMP = [[]] * m
for i in range(m):
  p, y = map(int, input().split())
  Year_lis = PY[p]
  insort(Year_lis, y)
  PY[p] = Year_lis
  IMP[i] = [p, y]
#print(PY)
#for key in PY.keys():
#  PY[key] = sorted(PY[key])
for imp in IMP:
  print("{:0=6}".format(imp[0]), end="")
  pos = PY[imp[0]].index(imp[1])
  print("{:0=6}".format(pos))

### FIXED CODE ###

n, m = map(int, input().split())
L = []
for i in range(m):
  L.append([i] + list(map(int, input().split() + ["000000000000"])))
L.sort(key=lambda x:(x[1], x[2]))
#print(L)

counter = 1
city = 0
for i in range(m):
  if city == L[i][1]:
    counter += 1
  else:
    counter = 1
  L[i][3] = str(L[i][1]).zfill(6) + str(counter).zfill(6)
  city = L[i][1]
#print(L)
L.sort(key=lambda x:x[0])
for i in range(m):
  print(L[i][3])
### BUGGY CODE ###

import numpy as np

n, k, q = map(int, input().split())
A = [int(input())-1 for i in range(q)]
P = np.ones(n) * k

for a in A:
    P[:a] -= 1
    P[a+1:] -= 1

P = np.where(P > 0, 'Yes', 'No')
for p in P:
    print(p)


### FIXED CODE ###

import numpy as np

n, k, q = map(int, input().split())
A = [int(input())-1 for i in range(q)]
P = np.ones(n) * k - q
for a in A:
    P[a] += 1
P = np.where(P > 0, 'Yes', 'No')
for p in P:
    print(p)
### BUGGY CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
sys.setrecursionlimit(10**7)
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    stack = []
    seen[1] = True
    heappush(stack, (0, 1, 0))# (distance, node, prev)
    mark = [0] * (N+1)

    while stack:
        dist, current, prev = heappop(stack)
        if not seen[current]:
            seen[current] = True
            mark[current] = prev
        for next in to[current]:
            if not seen[next]:
                heappush(stack, (dist+1, next, current))

    print('Yes')
    mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    queue = deque([])
    seen[1] = True
    queue.append((1, 0))# (node, prev)
    mark = [0] * (N+1)

    while queue:
        current, prev = queue.popleft()
        for next in to[current]:
            if not seen[next]:
                queue.append((next, current))
                mark[next] = current
                seen[next] = True

    print('Yes')
    mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

if __name__ == "__main__":
    run()
### BUGGY CODE ###

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

ans = 0
l = []
for i in range(N-2):
  for j in range(i+1, N-1):
    for k in range(j+1, N):
      s = S[i]+S[j]+S[k]
      if s not in l:
        l.append(s)
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = str(input())
R = S[::-1]

ans = 0
for i in range(1000):
  z = str(i).zfill(3)
  right = -1
  left = -1
  if z[2] in R:
    r = R.index(z[2]) + 1
    right = N-r
  else:
    continue
  if z[0] in S:
    left = S.index(z[0]) + 1
  else:
    continue
  if z[1] in S[left:right]:
    ans += 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
if sys.platform in ['ios', 'win32', 'darwin']:
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(x) for x in input().split()]

N = INT()
A = MAP()

R = sum(A)
# print(R)

M = [-1] * N

def solve(i):
	if i<N-1:
		if M[i] != -1:
			mi = M[i]
		else:
			mi = 2*A[i]-solve(i+1)
	else:
		mi = 2*A[i]-solve(0)
	return mi

# print(M)
M[0] = 0
s = 0
for i in range(N):
	s += solve(i)
# print(s)
M[0] += (R-s)

ans = [solve(i) for i in range(N)]
print(' '.join(map(str, ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
if sys.platform in ['ios', 'win32', 'darwin']:
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(x) for x in input().split()]

def main():
	N = INT()
	A = MAP()

	R = sum(A)
	# print(R)

	def solve(i):
		if i<N-1:
			if M[i] != -1:
				mi = M[i]
			else:
				mi = 2*A[i]-solve(i+1)
				M[i] = mi
		else:
			mi = 2*A[i]-solve(0)
			M[i] = mi
		return mi

	# print(M)
	M = [-1] * N
	M[0] = 0
	s = 0
	for i in range(1, N):
		s += solve(i)
	# print(s)

	M = [-1] * N
	M[0] = (R-s)

	ans = [solve(i) for i in range(N)]
	print(' '.join(map(str, ans)))

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

n,m=map(int,input().split())
l=[0]*m
for i in range(m):
    l[i]=int(input())
#print(l)
dp=[0]*(n+1)
dp[0]=1
for j in range(1,n+1):
    if j not in l:
        dp[j]=-1
#print(dp)
if dp[1]==-1:dp[1]=1
for i in range(2,n+1):
    if dp[i]==-1:
        dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
a=[-1]
for i in range(m):
    s=int(input())
    a.append(s)  
a.append(n+1)
if 1 in a:
    a=a[1:]
if n-1 in a:
    a=a[:-1]
b=[]
for i in range(len(a)-1):
    b.append(a[i+1]-a[i]-2)
l=[1,1,2]
for i in range(3,n+1):
    l.append(l[i-2]+l[i-1])
ans=1
#print(a,b,l)
for i in range(len(b)):
    if b[i]<0:
        print(0)
        break
    else:
        ans*=l[b[i]]%1000000007
else:
    print(ans%1000000007)