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

import sys
input = sys.stdin.readline
N,K = map(int,input().split())
A = [int(i) for i in input().split()]
loop = min(41,K)
for _ in range(loop):
    B = [0]*N
    for n in range(N):
        l = max(0,n-A[n])
        r = min(N-1,n+A[n])
        #print(l,r)
        B[l]+=1
        if r+1<N:
            B[r+1] -= 1
    #print(B)
    for n in range(1,N):
        B[n] += B[n-1]
    A = B
print(*A)

### FIXED CODE ###

N,K = map(int,input().split())
A = [int(i) for i in input().split()]
loop = min(41,K)
for _ in range(loop):
    B = [0]*N
    for n in range(N):
        l = max(0,n-A[n])
        r = min(N-1,n+A[n])
        B[l]+=1
        if r+1<N:
            B[r+1] -= 1
    for n in range(1,N):
        B[n] += B[n-1]
    A = [b for b in B]
print(*A)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i, n + 1):
        if sum(a[i:j]) == 0 and len(a[i:j]) > 0:
            ans += 1
print(ans)

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
a_t = [0]
for i in range(n):
    a_t.append(a[i] + a_t[i])
a_t = collections.Counter(sorted(a_t))
ans = 0
for i in a_t.values():
    ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

q = 3 if S[0] == '?' else 1
a = b = c = 0
if S[0] in 'A?':
    a = 1
for s in S[1:]:
    if s == '?':
        c = c * 3 + b
        b = b * 3 + a
        a = a * 3 + q
        q *= 3
    elif s == 'A':
        a += q
    elif s == 'B':
        b += a
    elif s == 'C':
        c += b

ans = c % MOD
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0, 0, 0, 0]
dp[0] = 1

for s in S:
    factor = 3 if s == '?' else 1
    for j, c in zip([2, 1, 0], 'CBA'):
        dp[j + 1] = dp[j + 1] * factor % MOD
        if s == c or s == '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] = (dp[0] * 3) % MOD

ans = dp[-1] % MOD

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

h, n = map(int, input().split())
inf = 1001001001
dp = [inf for _ in range(h+1)]
dp[0] = 0
ans = inf
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h + 1):
        # 外側参照しないように
        nj = min(j+a, h)
        dp[nj] = min(dp[nj], dp[j]+b)

print(dp[h])


### FIXED CODE ###

h, n = map(int, input().split())
inf = 1001001001
dp = [inf for _ in range(h+1)]
dp[0] = 0
ans = inf
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h + 1):
        # 外側参照しないように
        nj = min(j+a, h)
        dp[nj] = min(dp[nj], dp[j]+b)

print(dp[h])
### BUGGY CODE ###

from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *
input=lambda :sys.stdin.readline().rstrip()
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

lst=[]
for w,v in WV:
    for i in range(len(lst)):
        w1,v1=lst[i]
        if w1:
            lst.append([w1+w,v1+v])
    lst.append([w,v])

    lst=sorted(lst,key=lambda x:x[0],reverse=True)
    while lst and lst[-1][0]==0:
        lst.pop()

    w,v=lst[-1]
    for i in range(len(lst)-1)[::-1]:
        w1,v1=lst[i]
        if v1<=v:
            lst[i][0]=0
            lst[i][1]=0
        else:
            v1=v
print(max([v for w,v in lst if w<=W]))


### FIXED CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
import sys
input = sys.stdin.readline
from heapq import*


N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]
dp=[[0 for i in range(301*(N+1))] for n in range(N)]
Z=WV[0][0]

for i in range(N):
    WV[i][0]-=Z
for n in range(N):
    for i in range(len(dp[0])):
        w,v=WV[n]
        if n==0:
            dp[n][w+301]=v
        else:
            dp[n][w+301]=max(dp[n-1][w+301],v)
            if i>=w+301:
                if dp[n-1][i-(w+301)]:
                    dp[n][i]=max(dp[n-1][i-(w+301)]+v,dp[n-1][i])
                else:
                    dp[n][i]=dp[n-1][i]
            else:
                dp[n][i]=dp[n-1][i]


print(max([max([dp[n][i] for i in range(len(dp[0])) if W>=i//301*Z+i%301]) for n in range(N)]))
### BUGGY CODE ###

N = int(input())
nums = []
for i in range(N):
    nums.append(int(input()))

for i in range(N):
    print(max(nums[0:i] + nums[i+1:]))

### FIXED CODE ###

N = int(input())
nums = []
for i in range(N):
    nums.append(int(input()))

maxinum = max(nums)
maxinum2 = -1
for i in range(N):
    if nums[i] == maxinum:
        if maxinum2 == -1:
            maxinum2 = max(nums[0:i] + nums[i+1:])
        print(maxinum2)
    else:
        print(maxinum)
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = np.array(a) % k
cumsum = np.cumsum(a)
cumsum = np.hstack([[0], cumsum])

count = 0
for l in range(len(cumsum)):
    for r in range(l + 1, len(cumsum)):
        s = cumsum[r] - cumsum[l]
        if r - l == s % k:
            count += 1
#             print(cumsum[r] - cumsum[l])
print(count)

### FIXED CODE ###

from collections import defaultdict
import numpy as np
n,k=map(int,input().split())
a=[0]+list(np.cumsum(list(map(int,input().split()))))

dic = defaultdict(int)
c = 0
for i in range(len(a)):
    p = (a[i] - i) % k
    c += dic[p]
    dic[p] += 1
    if i >= k - 1:
        dic[(a[i - k + 1] - (i - k + 1)) % k] -= 1
print(c)
### BUGGY CODE ###

import sys
import  math
from statistics import *
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
aaa = na()
bbb = na()
ccc = na()
aaa.sort()
bbb.sort()
ccc.sort()
l = 0
r = 0
ct = 0
for i in range(n):
    for j in range(n):
        if aaa[i] < bbb[j]:
            for k in range(n):
                if bbb[j] < ccc[k]:
                    ct += n - k
                    break
print(ct)

### FIXED CODE ###

import sys
import  math
import bisect
from statistics import *
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
aaa = na()
bbb = na()
ccc = na()
aaa.sort()
ccc.sort()
l = 0
r = 0
ct = 0
ct = 0
for i in range(n):
    l = bisect.bisect_left(aaa, bbb[i])
    r = bisect.bisect_right(ccc, bbb[i])
    ct += l * (n - r)

print(ct)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
    b.append((a.index(i+1))+1)
print(*b)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0 for k in range(n)]
for i in range(n):
    b[a[i]-1] = i+1
print(*b)
### BUGGY CODE ###

from fractions import Fraction

class Combination:
    '''計算量：階乗・逆元テーブルの作成O(N)
       nCkを求めるO(1)'''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i] ,MOD - 2 ,MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        '''k!を求める'''
        return self.fact[k]

    def inverse_factorial(self, k):
        '''k!の逆元を求める'''
        return self.inv_fact[k]

    def combination(self, k, r):
        '''kCrを求める'''
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


b, w = map(int,input().split())
MOD = 10**9 + 7
comb = Combination(b+w, MOD)

#黒が(b+w-i)個残る確率 := pb
#白が(b+w-i)個残る確率 := pw
pb = [0]*(b+w+1)
pw = [0]*(b+w+1)

for i in range(b+w):
    if b+w-i > b:
        pb[b+w-i] = 0
        result_b = Fraction(0)
    else:
        result_b = Fraction(pb[b+w-i+1]) \
                 + Fraction(1, pow(2, i, MOD)) * Fraction(comb.combination(i-1, w-1) % MOD)
        pb[b+w-i] = Fraction(result_b.numerator % MOD, result_b.denominator % MOD)
        
    if b+w-i > w:
        pw[b+w-i] = 0
        result_w = Fraction(0)
    else:
        result_w = Fraction(pw[b+w-i+1]) \
                 + Fraction(1, pow(2, i, MOD)) * Fraction(comb.combination(i-1, b-1) % MOD)
        pw[b+w-i] = Fraction(result_w.numerator % MOD, result_w.denominator % MOD)
        
    ans = Fraction(result_b) \
          + Fraction(1, 2) * (Fraction(1) - Fraction(result_b) - Fraction(result_w))
    y = ans.numerator % MOD
    x = ans.denominator % MOD
    
    print((y * pow(x, MOD-2, MOD)) % MOD)
        

### FIXED CODE ###

from fractions import Fraction

class Combination:
    '''計算量：階乗・逆元テーブルの作成O(N)
       nCkを求めるO(1)'''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i] ,MOD - 2 ,MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        '''k!を求める'''
        return self.fact[k]

    def inverse_factorial(self, k):
        '''k!の逆元を求める'''
        return self.inv_fact[k]

    def combination(self, k, r):
        '''kCrを求める'''
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


b, w = map(int,input().split())
MOD = 10**9 + 7
comb = Combination(b+w, MOD)

#黒が(b+w-i)個残る確率 := pb
#白が(b+w-i)個残る確率 := pw
pb = [0]*(b+w+1)
pw = [0]*(b+w+1)

for i in range(b+w):
    if b+w-i > b:
        pb[b+w-i] = 0
        result_b = 0
    else:
        result_b = pb[b+w-i+1] + pow(pow(2, i, MOD), MOD-2, MOD) * comb.combination(i-1, w-1)
        result_b %= MOD
        pb[b+w-i] = result_b
        
    if b+w-i > w:
        pw[b+w-i] = 0
        result_w = 0
    else:
        result_w = pw[b+w-i+1] + pow(pow(2, i, MOD), MOD-2, MOD) * comb.combination(i-1, b-1)
        result_w %= MOD
        pw[b+w-i] = result_w
        
    ans = result_b + pow(2, MOD-2, MOD) * (1 - result_b - result_w)
    print(ans % MOD)
### BUGGY CODE ###


#E
N,P=map(int,input().split())
S=input()
ans=0
if P in (2,5):
    for i,s in enumerate(S):
        if int(s)%P==0:
            ans+=i+1
else:
    cnt=[0 for _ in range(P)]
    CS=0
    for i,s in enumerate(S[::-1]):
        tmp2=(10**i)%P
        tmp=(int(s)*tmp2)%P
        CS=(CS+tmp)%P
        cnt[CS]+=1
        # print(CS)
        # print(cnt)
    for c in cnt:
        ans+=c*(c-1)//2
    ans+=cnt[0]
print(ans)

### FIXED CODE ###

#E
N,P=map(int,input().split())
S=input()
ans=0
if P in (2,5):
    for i,s in enumerate(S):
        if int(s)%P==0:
            ans+=i+1
else:
    cnt=[0 for _ in range(P)]
    CS=0
    PLC=1
    for s in S[::-1]:
        tmp=(int(s)*PLC)%P
        CS=(CS+tmp)%P
        cnt[CS]+=1
        PLC=(PLC*10)%P
        # print(CS)
        # print(cnt)
    for c in cnt:
        ans+=c*(c-1)//2
    ans+=cnt[0]
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')]*N
dp[0] = 0
 
 
for i in range(1,N):
    l = min(K,i)
    data = []
    dp[i] = min(dp[i-j]+abs(h[i] - h[i-j]) for j in range(1,l+1))
print(dp[N-1])

### FIXED CODE ###

def test():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf')]*N
    dp[0] = 0
 
    for i in range(1, N):
        dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i-K, 0), i))
 
    print(dp[-1])
 
if __name__ == '__main__':
    test()
### BUGGY CODE ###

def longestRepeatedSubstring(str):

    n = len(str)
    LCSRe = [[0 for x in range(n + 1)]
             for y in range(n + 1)]

    res = ""
    res_length = 0

    index = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if (str[i - 1] == str[j - 1] and
                    LCSRe[i - 1][j - 1] < (j - i)):
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1

                if (LCSRe[i][j] > res_length):
                    res_length = LCSRe[i][j]
                    index = max(i, index)

            else:
                LCSRe[i][j] = 0


    if (res_length > 0):
        for i in range(index - res_length + 1,
                       index + 1):
            res = res + str[i - 1]

    return res


if __name__ == "__main__":
    a = int(input())
    s = input()

    print(len(longestRepeatedSubstring(s)))


### FIXED CODE ###

def lrs(str):
    n = len(str)
    LCSRe = [[0 for x in range(n + 1)]
             for y in range(n + 1)]
    res = ""
    res_length = 0
    index = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if (str[i - 1] == str[j - 1] and
                    LCSRe[i - 1][j - 1] < (j - i)):
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1

                if (LCSRe[i][j] > res_length):
                    res_length = LCSRe[i][j]
                    index = max(i, index)

            else:
                LCSRe[i][j] = 0


    if (res_length > 0):
        for i in range(index - res_length + 1,
                       index + 1):
            res = res + str[i - 1]

    return res


if __name__ == "__main__":
    a = int(input())
    s = input()

    print(len(lrs(s)))
### BUGGY CODE ###

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

sumpro = 0
for i in range(N):
	for j in range(i + 1, N):
		sumpro += A[i] * A[j]

print(sumpro % 1000000007)


### FIXED CODE ###

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

s = sum(A)
sumpro = 0

for a in A[:-1]:
	s -= a
	sumpro += a * s

print(sumpro % (10 ** 9 + 7))
### BUGGY CODE ###

import collections as c

h,w,m = map(int,input().split())
x = []
y = []
z = []
for i in range(m):
    s,t = map(int,input().split())
    x.append(s)
    y.append(t)
    z.append(tuple([s,t]))
a = c.Counter(x)
b = c.Counter(y)
a = a.most_common()
b = b.most_common()
c = []
d = []
e = a[0][1]
f = b[0][1]

for sa in a:
    if sa[1] == e:
        c.append(sa[0])
    else:
        break
for sb in b:
    if sb[1] == f:
        d.append(sb[0])
    else:
        break

fl = 0
ans = e+f-1
for s in c:
    for t in d:
        if tuple([s,t]) not in z:
            fl = 1
            ans += 1
            break
    if fl == 1:
        break
    
print(ans)

### FIXED CODE ###

import collections as c

h,w,m = map(int,input().split())
x = []
y = []
z = set([])
for i in range(m):
    s,t = map(int,input().split())
    x.append(s)
    y.append(t)
    z.add(tuple([s,t]))
a = c.Counter(x)
b = c.Counter(y)
a = a.most_common()
b = b.most_common()
c = []
d = []
e = a[0][1]
f = b[0][1]

for sa in a:
    if sa[1] == e:
        c.append(sa[0])
    else:
        break
for sb in b:
    if sb[1] == f:
        d.append(sb[0])
    else:
        break

fl = 0
ans = e+f-1
for s in c:
    for t in d:
        if tuple([s,t]) not in z:
            fl = 1
            ans += 1
            break
    if fl == 1:
        break
    
print(ans)
### BUGGY CODE ###

import sys	

num1 = list(map(int, input().split()))
N = num1[0] #参加者数
K = num1[1] #初期ポイント
Q = num1[2] #出た正解の数
ans_list = []
for index0 in range(Q):
	ans_list.append(int(input()))
for index1 in range(1,N+1):
	point = 0
	point=ans_list.count(index1)

	fin=K+point-Q

	
	if fin <=0:
		print("No")
	else:
		print("Yes")
		

### FIXED CODE ###

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

class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n
        # one -index
        # self.g  = [set([i]) for i in range(n+1)]
        # self.gp = [set([i]) for i in p]

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # self.g[y+1] = self.g[y+1] | self.g[x+1]
            # self.gp[y+1]= self.gp[y+1]| self.gp[x+1]
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

    def same(self, x, y):
        return self.find(x) == self.find(y)

def main():
    n,m = map(int,input().split())
    p = [set([int(i)]) for i in input().split()]
    r = [set([int(i)]) for i in range(1,n+1)]
    uf = UnionFind(n)
    for i in range(m):
        x,y = map(int,input().split())
        uf.unite(x-1,y-1)
    parent = set()
    for i in range(n):
        parent.add(uf.find(i))
        p[uf.find(i)] = p[uf.find(i)] | p[i]
        r[uf.find(i)] = r[uf.find(i)] | r[i]

    ans = 0
    for i in parent:
        ans += len(p[i]) + len(r[i]) - len(p[i] | r[i])
    print(ans)
main()


### FIXED CODE ###

class UnionFind:
    def __init__(self, n, p):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

    def same(self, x, y):
        return self.find(x) == self.find(y)

def main():
    n,m = map(int,input().split())
    p = list(map(int,input().split()))

    uf = UnionFind(n,p)
    for i in range(m):
        x,y = map(int,input().split())
        uf.unite(x-1,y-1)

    ans = 0
    for i,j in enumerate(p):
        ans += uf.same(i, j-1)
    print(ans)
main()
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    d = list(map(int,input().split()))
    cnt=0

    d.sort()
    a=d[0]
    b=d[n-1]
    c=b-a+1

    for i in range(c):
        index=bisect.bisect_right(d,i+a)
        D=d[index:]
        lend=len(D)
        if(int(n//2)==lend):
            cnt+=1
    
    print(cnt)
    
main()


### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    d = list(map(int,input().split()))
    cnt=0

    d.sort()
    a=d[(n//2)-1]
    b=d[(n//2)]
    ans=b-a
    print(ans)
    
main()
### BUGGY CODE ###

import heapq
 
H, W = [int(x) for x in input().split()]
c_h, c_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
d_h, d_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
s = [['.' for w in range(W)] for h in range(H)]
for h in range(H):
    s[h] = input()
 
def in_the_map(x):
    if x[0] < 0 or H <= x[0] or x[1] < 0 or W <= x[1]:
        return False
    return True
 
visited = [[False for w in range(W)] for h in range(H)]
queue = []
heapq.heappush(queue, (0, (c_h, c_w)))  # Push start point with cost (number of warps) 0
 
while len(queue) > 0:
    cost, p = heapq.heappop(queue)
 
    if visited[p[0]][p[1]]:  # Skip if already visited (the priority queue assures we can visit to the point with the smallest cost)
        continue
    visited[p[0]][p[1]] = True
 
    if p[0] == d_h and p[1] == d_w:  # Finally reach to the goal
        print(cost)
        break
    # print(f'Visit {p}: {cost}')
 
    # Explore neighbours where can be reached by walk (with the same cost as p)
    neighbours = ((p[0], p[1] - 1), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0] + 1, p[1]))
    for n in neighbours:
        if not in_the_map(n) or visited[n[0]][n[1]]:
            continue
        if s[n[0]][n[1]] == '.':  # not wall
            heapq.heappush(queue, (cost, n))  # For later exploration
 
    # Explore points where can be reached by warp from visited points(with +1 cost from p)
    for diff_h in range(-2, 3, 1):
        for diff_w in range(-2, 3, 1):
            h = p[0] + diff_h
            w = p[1] + diff_w
            if not in_the_map((h, w)) or visited[h][w]:
                continue
            if s[h][w] == '.': # not wall
                heapq.heappush(queue, (cost + 1, (h, w)))
 
if not visited[d_h][d_w]:  # Cannot reach to the goal
    print(-1)

### FIXED CODE ###

H, W = [int(x) for x in input().split()]
c_h, c_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
d_h, d_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
s = [['.' for w in range(W)] for h in range(H)]
for h in range(H):
    s[h] = input()

def in_the_map(x):
    if x[0] < 0 or H <= x[0] or x[1] < 0 or W <= x[1]:
        return False
    return True
 
costs = [[-1 for w in range(W)] for h in range(H)]
 
def dfs(h, w, c, q):
    if not in_the_map((h, w)):
        return
    if costs[h][w] >= 0:
        return
    if s[h][w] != '.':
        return
    q.append((h, w))
    costs[h][w] = c 
    dfs(h - 1, w, c, q)
    dfs(h + 1, w, c, q)
    dfs(h, w - 1, c, q)
    dfs(h, w + 1, c, q)

queue = [(c_h, c_w)]
cost = 0
while len(queue) > 0:
    visited = []
    for q in queue:
        dfs(q[0], q[1], cost, visited)
    
    next_queue = []
    for v in visited:
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh = v[0] + dh 
                ww = v[1] + dw
                if not in_the_map((hh, ww)):
                    continue
                if costs[hh][ww] >= 0:
                    continue
                if s[hh][ww] != '.':
                    continue
                next_queue.append((hh, ww))

    cost += 1
    queue = next_queue

print(costs[d_h][d_w])
### BUGGY CODE ###

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

inv = [i for i in range(N-1)]
visited = [1]

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

for i in range(M):
  A, B = map(int, input().split())
  path[A].append(B)
  path[B].append(A)
nows = [1]
for t in range(N):
  buf = []
  for now in nows:
    for p in path[now]:
      if p not in visited:
        buf.append(p)
        visited.append(p)
        inv[p-2]=now
  if len(buf)==0:
    break
  nows = buf
print("Yes")
for i in inv:
  print(i)


### FIXED CODE ###

import queue

q = queue.Queue()
N, M = map(int, input().split())

ans = [-1 for i in range(N+1)]
path = [[] for i in range(N+1)]

for i in range(M):
  A, B = map(int, input().split())
  path[A].append(B)
  path[B].append(A)
q.put(1)
COUNTER = 0
while not q.empty() :
  now = q.get()
  for p in path[now]:
    if ans[p]==-1:
      ans[p]=now
      q.put(p)
      #print(COUNTER, now,p)
      COUNTER+=1
      
print("Yes")
for i in ans[2:]:
  print(i)