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

H,W = map(int,input().split())
A = ['' for i in range(H)]
colors = [[-2 for j in range(W)] for i in range(H)]
q = []
for i in range(H):
    A[i] = list(input())
    for j,color in enumerate(A[i]):
        colors[i][j] = 0 if color == '#' else -1
        if '#' == color:
            q.append([i,j,0])
# for i in colors:
#     print(i)
mx = 0
direction = [[1,0],[0,1],[-1,0],[0,-1]]
while len(q) > 0:
    # print(q)
    tmp = [y,x,op] = q.pop(0)
    mx = max(mx,op)
    if colors[y][x] > 0: continue
    colors[y][x] = op
    for [dx,dy] in direction:
        ny,nx = y + dy , x + dx
        if  0 <= ny and ny < H and 0 <= nx and nx < W:
            if A[ny][nx] == '#' or colors[ny][nx] >= 0:
                continue
            q.append([ny,nx,op+1])
print(mx)

### FIXED CODE ###

from sys import stdin
from collections import deque
def main():
    readline = stdin.readline
    H,W = map(int,readline()[:-1].split())
    A = ['' for i in range(H)]
    visited = [[False] * W for i in range(H)]
    q = deque()
    for i in range(H):
        A[i] = readline()[:-1]
        # print(A[i])
        for j,color in enumerate(A[i]):
            if '#' == color:
                q.append([i,j,0])
                visited[i][j] = True
            # for i in visited:
            #     print(i)
    mx = 0
    direction = [[1,0],[0,1],[-1,0],[0,-1]]
    op = -1
    while len(q) > 0:
        # print(q)
        tmp = [y,x,op] = q.popleft()
        # print(tmp)
        mx = mx if mx > op else op
        for [dx,dy] in direction:
            ny,nx = y + dy , x + dx
            if  0 <= ny and ny < H and 0 <= nx and nx < W:
                if A[ny][nx] == '#' or visited[ny][nx] == True:
                    continue
                q.append([ny,nx,op+1])
                visited[ny][nx] = True
    print(op)

main()
### BUGGY CODE ###

S = input()

a = [0] * (len(S) + 1)
S = "*" + S + "*"
for i in range(len(a)):
    left_str = S[:i+1]
    right_str = S[i+1:]

    left_cnt = len(left_str) - len(left_str.rstrip("<"))
    right_cnt = len(right_str) - len(right_str.lstrip(">"))

    a[i] = max(left_cnt, right_cnt)

print(sum(a))

### FIXED CODE ###

S = input()

left_count = [0] * (len(S) + 1)
right_count = [0] * (len(S) + 1)

S = "*" + S + "*"
cur_left_count = 0
cur_right_count = 0
for i in range(len(left_count)):
    if S[i] == "<":
        cur_left_count += 1
    else:
        cur_left_count = 0

    if S[-i-1] == ">":
        cur_right_count += 1
    else:
        cur_right_count = 0
    
    left_count[i] = cur_left_count
    right_count[-i-1] = cur_right_count

a =  [max(l, r) for l, r in zip(left_count, right_count)]

print(sum(a))
### BUGGY CODE ###

import math
Q = int(input())

l = []
r = []
while True:
  try:
    lr=list(map(int,input().split()))
    l.append(lr[0])
    r.append(lr[1])
  except:
    break

def is_prime(num):
  if(type(num) != type(0)):
    print('error at '+str(num)+' type = '+str(type(num)))
    print(type(int))
    return 0
  if(num<2):
    return 0
  elif(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  sn = [0]
  for i in range(1,MAXI+1,2):
    sn.append(is_prime(i) * is_prime(int((i+1)/2))) #odd
    sn.append(0) #even
  return sn

base = create_list()

for i in range(Q):
  if(l[i]==r[i]):
    print(base[l[i]])
  else:
    lnum = base[0:l[i]]
    rnum = base[0:r[i]]
    print( sum(rnum)-sum(lnum) )

### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)

Q = int(input())

l = [0 for _ in range(Q)]
r = [0 for _ in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  #if(type(num) != type(0)):
  #  print('error at '+str(num)+' type = '+str(type(num)))
  #  print(type(int))
  #  return 0
  #if(num<2):
  #  return 0
  if(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for _ in range(MAXI+1)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i*2,MAXI,i*2):
        prime[j] = 0
      for j in range(i*5,MAXI,i*3):
        prime[j] = 0
      for j in range(i*5,MAXI,i*5):
        prime[j] = 0
  #print(prime)
  sn = [0 for _ in range(MAXI+2)]
  for i in range(1,MAXI+1,2):
    #print('int(('+str(i+1)+')/2) = '+str(int((i+1)/2))+' when '+str(prime[int((i+1)/2)]))
    sn[i] += sn[i-1] + (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = sn[i]
  return sn

base = create_list()
#print(base)
for i in range(Q):
  print( base[r[i]] - base[l[i]-1] )#sum(rnum)-sum(lnum) )
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
l = 0
r = n - 1
print(l)
ltmp = STR() #初期状態 偶数席
if ltmp == 'Vacant':
    exit()
print(r)
rtmp = STR() #最終状態 奇数
if rtmp == 'Vacant':
    exit()
while l < r:
    c = (l + r) // 2
    print(c)
    tmp = STR()
    if tmp == 'Vacant':
        exit()
    if c % 2 == l % 2:
        if tmp == ltmp:
            l = c + 1
        else:
            r = c - 1
    else:
        if tmp == ltmp:
            r = c - 1
        else:
            l = c + 1

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
l = 0
r = n - 1
print(l, flush=True)
ltmp = STR()
if ltmp == 'Vacant':
    exit()
print(r, flush=True)
rtmp = STR()
if rtmp == 'Vacant':
    exit()
for i in range(2, 20):
    c = (l + r) // 2
    print(c, flush=True)
    tmp = STR()
    if tmp == 'Vacant':
        exit()
    if c % 2 == l % 2:
        if tmp == ltmp:
            l = c
            ltmp = tmp
        else:
            r = c
    else:
        if tmp == ltmp:
            r = c
        else:
            l = c
            ltmp = tmp
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

rmax = N // R + 1

ans = 0
for i in range(rmax):
    gmax = (N - i * R) // G + 1
    for j in range(gmax):
        if (N - (i * R + j * G)) % B == 0 and (N - (i * R + j * G)) >= 0:
            ans += 1  
print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(int(N / R) + 1):
    for j in range(int((N - i * R) / G) + 1):
        if ((N - (i * R + j * G)) % B == 0):
            ans += 1
print(ans)
### BUGGY CODE ###

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

fact = [0] * (N + 1)
inv = [0] * (N + 1)
fact[0] = 1
inv[0] = pow(1, MOD - 2, MOD)

for i in range(1, N + 1) :
    fact[i] = (fact[i-1] * i) % MOD
    inv[i] = pow(fact[i], MOD - 2, MOD)

mem = [[-1] * (N + 1) for _ in range(N + 1)]

def comb(n, r) :
    if n < r or n < 0 or r < 0 :
        return 0
    if mem[n][r] >= 0 :
        return mem[n][r]
    else :
        mem[n][r] = (fact[n] * inv[n-r] * inv[r]) % MOD
        return mem[n][r]

ret = 0
n1 = [0] * (N + 1)

sum = 0
for k, v in enumerate(L) :
    if v == '1' :
        for i in range(N-k) :
            n1[sum+i] += comb(N-k-1, i)
        sum += 1

n1[L.count('1')] += 1
   
for i, n in enumerate(n1) :
    ret += n * pow(2, i, MOD)
    ret %= MOD
    
print(ret)

### FIXED CODE ###

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

s = 0
ret = 0
for k, v in enumerate(L) :
    if v == '1' :
        ret += pow(2, s, MOD) * pow(3, N-k-1, MOD)
        ret %= MOD
        s += 1

ret += pow(2, s, MOD)

print(ret % MOD)
### BUGGY CODE ###

def main():
    
    s = list(input())
    mod = 10**9+7
    dp = [[0]*13 for i in range(len(s)+1)]
    dp[0][0] = 1
    ten = 1


    for i in range(len(s)):
        if s[-1-i] == "?":
            for k in range(10):
                x = k*ten%13
                for j in range(13):
                    dp[i+1][(j+x)%13] += dp[i][j]
        
        else:
            x = int(s[-1-i])*ten%13
            for j in range(13):
                dp[i+1][(j+x)%13] += dp[i][j]%mod

        ten *= 10%mod

    print(dp[-1][5]%mod)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    
    s = input()[::-1]
    mod = 10**9+7
    dp = [[0 for j in range(13)] for i in range(len(s)+1)]
    dp[0][0] = 1
    ten = 1


    for i in range(len(s)):
        if s[i] == "?":
            for k in range(10):
                x = k*ten%13
                for j in range(13):
                    dp[i+1][(j+x)%13] = (dp[i][j]+dp[i+1][(j+x)%13])%mod
        
        else:
            x = int(s[i])*ten%13
            for j in range(13):
                dp[i+1][(j+x)%13] = (dp[i][j]+dp[i+1][(j+x)%13])%mod

        ten = (ten*10)%13

    print(dp[-1][5]%mod)

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

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def main():
    n = int(input())
    As = [int(input()) for i in range(n)]
    mn = max(As)
    for i in range(n):
        if As[i] == mn:
            print(max(As[:i] + As[i+1:]))
        else:
            print(mn)
    return 

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def main():
    n = int(input())
    As = [int(input()) for i in range(n)]
    sAs = sorted(As)
    mn1 = sAs[-1]
    mn2 = sAs[-2]
    for i in range(n):
        if As[i] == mn1:
            print(mn2)
        else:
            print(mn1)
    return 

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

N = int(input())
count = 0
word = []
def verify_anagrams(w1, w2):
    f = lambda y: "".join(sorted(map(lambda x: x.replace(' ', '').lower(), y)))
    return f(w1) == f(w2)

def str_sort(str):
    f = lambda y: "".join(sorted(map(lambda x: x.replace(' ', '').lower(), y)))
    return f(str)
for _ in range(N):
    word.append(str_sort(input()))


for i in range(N - 1):
    for j in range(i + 1,N):
        if word[i] ==  word[j]:
            count += 1
print(count)

### FIXED CODE ###

#from Collections import Counter

N = int(input())
count = 0
word = {}
def str_sort(str):
    f = lambda y: "".join(sorted(map(lambda x: x.replace(' ', '').lower(), y)))
    return f(str)
for _ in range(N):
    sorted_str = str_sort(input())
    if sorted_str not in word:
        word[sorted_str] = [0]
        word[sorted_str].append(1)
    else:
        if word[sorted_str] == 0:
            word[sorted_str][0] = 1
        else:
            word[sorted_str][0] += word[sorted_str][1]
            word[sorted_str][1] += 1
            #word[sorted_str] = word[sorted_str][0] + word[sorted_str][1]
total = sum(
    v[0] for v in word.values()
)
#print(word)
print(total)
### BUGGY CODE ###

n=int(input())
count=0
scount=0
listcount=0
anslist=[]
s=[]
for i in range(n):
    a=input()
    s.append(a)
s_count=s.count
s.sort()
for i in range(n):
    if listcount==n:
        break
    scount=s_count(s[listcount])
    if scount>count:
        count=scount
        anslist.clear()
        anslist.append(s[listcount])
    elif scount==count:
        anslist.append(s[listcount])
    listcount+=scount
anslist.sort()
for i in range(len(anslist)):
    print(anslist[i])


### FIXED CODE ###

from collections import Counter
n=int(input())
list=[input() for _ in range(n)]
list.sort()
c=Counter(list).most_common()
most=c[0][1]
c.sort()
for i in range(len(c)):
    if c[i][1]==most:
        print(c[i][0])
### BUGGY CODE ###

import sys
for line in sys.stdin:
    n = int(line)
    arr = [i for i in range(0,n+1)]
    k = 2
    while k**2 <= n:
        for i in range(len(arr)):
            if arr[i]%k == 0 and arr[i] != 2:
                arr[i] = 0
        print(k, arr)
        k += 1
    count = 0
    for i in range(len(arr)):
        if arr[i] != 0 and arr[i] != 1:
            count += 1
    print(count)

### FIXED CODE ###

import sys
prime = [0]
isPrime = [1 for i in range(1000000)]
isPrime[0] = 0
isPrime[1] = 0
for i in sys.stdin:
    n = int(i)
    if prime[len(prime)-1] < n:
        for i in range(prime[len(prime)-1]+1,n+1):
            if isPrime[i] == 1:
                prime.append(i)
                for j in range(i*2, 1000000, i):
                    isPrime[j] = 0
    print(sum(isPrime[:n+1]))
### BUGGY CODE ###

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

s = 0

m = 1000000007

for i in range(n):

    if i == n-1:
        pass
    else:
        for j in range(i+1, n):
            s += a[i] * a[j]

s = s % m

print(s)


### FIXED CODE ###

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

m = 1000000007

s = sum(a)
ans = 0
for i in range(n):
    aa = a[i]
    ans += aa * (s - aa)

ans = ans//2
ans = ans % m

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

s = input()
k = int(input())

a = list(s)
a = [ord(i) for i in a]
m = 0
c = []
INF = 97+26
while len(c) < k:
    m = min(a, key=lambda x: x if x > m else INF)
    a1 = [i for i in range(len(s)) if a[i] == m]
    for i in a1:
        j = 0
        while i+j < len(s):
            if s[i:i+j+1] not in c:
                c.append(s[i:i+j+1])
            j += 1

c.sort()
print(c[k-1])




### FIXED CODE ###

s = input()
k = int(input())

a = list(s)
a = [ord(i) for i in a]
b = sorted(set(a))
c = []
INF = 97+26
for m in b:
    a1 = [i for i in range(len(s)) if a[i] == m]

    for i in a1:
        j = 0
        for j in range(k):
            if s[i:i+j+1] not in c:
                c.append(s[i:i+j+1])
                c.sort()
            if len(c) > 5:
                del c[-1]
            j += 1
            if i + j >= len(s):
                break
    if len(c) >= k:
        break

print(c[k-1])
### BUGGY CODE ###

from collections import deque

h , w = map(int,input().split())
ma = [["#"]*(w+2)]
cou = 0
for i in range(h):
    kar = ["#"]
    kar.extend(list(input()))
    cou += kar.count(".")
    kar.append("#")
    ma.append(kar)
ma.append(["#"]*(w+2))

ans = [[-1 for i in range(w+2)] for j in range(h+2)]
ans[1][1] = 1
q = deque([(1,1)])

while q:
    x , y = q.popleft()
    ma[x][y] = "#"
    if ma[x-1][y] == ".":
        q.append((x-1,y))
        ans[x-1][y] = ans[x][y] + 1
    if ma[x+1][y] == ".":
        q.append((x+1,y))
        ans[x+1][y] = ans[x][y] + 1        
    if ma[x][y-1] == ".":
        q.append((x,y-1))
        ans[x][y-1] = ans[x][y] + 1        
    if ma[x][y+1] == ".":
        q.append((x,y+1))
        ans[x][y+1] = ans[x][y] + 1

if ans[h][w] == -1:
    print(-1)
else:
    print(cou - ans[h][w])


### FIXED CODE ###

from collections import deque
 
h , w = map(int,input().split())
cou = 0
ma = []
for i in range(h):
    kar = list(input())
    cou += kar.count("#")
    ma.append(kar)
 
 
ans = [[-1 for i in range(w)] for j in range(h)]
ans[0][0] = 1
q = deque([(0,0)])
xy = [(1,0),(-1,0),(0,1),(0,-1)]
 
while q:
    x , y = q.popleft()
    for i in range(4):
        nx = x + xy[i][0]
        ny = y + xy[i][1]
        if 0 <= nx <= h-1 and 0 <= ny <= w-1 and ans[nx][ny] == -1:
            if ma[nx][ny] == ".":
                q.append((nx,ny))
                ans[nx][ny] = ans[x][y] + 1
        if nx == h-1 and ny == w-1:
            break
 
if ans[h-1][w-1] == -1:
    print(-1)
else:
    print(h*w - cou - ans[h-1][w-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import itertools

# 入力を変数に格納
count = int(input())
num_list = [int(i) for i in input().split()]

s = [0]
sum_tmp = 0
for num in num_list:
    sum_tmp += num
    s.append(sum_tmp)

pair_list = list(itertools.combinations(s, 2))

result = 0
for pair in pair_list:
    if pair[0] == pair[1]:
        result += 1

print(result)

### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/agc023/editorial.pdf
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, initial=1)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def nCr(n, r):
    # 10C7 = 10C3
    r = min(r, n-r)
    return factorial(n) // (factorial(r) * factorial(n-r))

N = INT()
aN = LIST()

sm = [0] * (N+1)
for i in range(N):
    sm[i+1] = sm[i] + aN[i]

c = Counter(sm)
ans = 0
for k, v in c.items():
    if v >= 2:
        ans += nCr(v, 2)
print(ans)
### BUGGY CODE ###

s=input()

ans=0
while "10" in s:
  s=s.replace("10","",1)
  ans+=1
while "01" in s:
  s=s.replace("01","",1)
  ans+=1
print(ans*2)

### FIXED CODE ###

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

f=lambda:map(int,input().split())
R,C,K=f()
g=[[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
  r,c,v=f()
  g[r][c]=v
dp=[[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
for i in range(1,R+1):
  for j in range(1,C+1):
    for k in range(3,-1,-1):
      if k: dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+ｇ[i][j])
      dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][k])
      dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k])
print(max(dp[R][C][k] for k in range(4)))

### FIXED CODE ###

f=lambda:map(int,input().split())
R,C,K=f()
g=[[0]*(R+1) for _ in range(C+1)]
for _ in range(K):
  r,c,v=f()
  g[c][r]=v
dp=[[0]*4 for _ in range(R+1)]
for i in range(1,C+1):
  for j in range(1,R+1):
    t=g[i][j]
    if t:
      for k in range(3,0,-1):
        dp[j][k]=max(dp[j][k],dp[j][k-1]+t)
      dp[j][1]=max(dp[j][k],max(dp[j-1])+t)
    dp[j][0]=max(dp[j][0],max(dp[j-1]))
print(max(dp[R]))
### BUGGY CODE ###

S = list(input())
N = len(S)
num = 0
cnt = [0]*2019
cnt[0] = 1
d = 1
#T[i]: i+1文字目以降を数とみなしたときの数
for i in range(N-1, -1, -1):
    num += int(S[i]) * d
    num %= 2019
    # num = (num + int(S[i]) * 10 ** (N- i -1)) % 2019
    cnt[num] += 1
    d *= 10

ans = 0
for c in cnt:
    ans += c * (c-1) // 2
print(ans)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

import sys
sys.setrecursionlimit(20000*20000)

S = str(input())
ans = set()
check = set()

def dfs(i, j):
    if (i, j) in check:
        return
    else:
        check.add((i, j))
    if int(S[i:j+1])%2019 == 0:
        ans.add((i, j))
        for k in range(1, j-i+1):
            check.add((i+k, j+k))
    if j == len(S)-1:
        return

    dfs(i+1, j+1)
    dfs(i, j+1)

if len(S) < 4:
    print(0)

else:
    dfs(0, 3)
    print(len(ans))

### FIXED CODE ###

s=input()
n=len(s)
mod=2019
d=0
p=1
ml=[0]*mod
for i in range(1,n+1):
  k=int(s[-i])
  d+=p*k
  d%=mod
  ml[d]+=1
  p*=10
  p%=mod
ans=0
for i in ml:
  ans+=i*(i-1)//2
print(ans+ml[0])
### BUGGY CODE ###

import numpy as np

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

network = [[] for _ in range(N+1)]

res = np.zeros((N+1), dtype="int32")
distance = np.full((N+1), N+1)
distance[1] = 0


for _ in range(M):
    i, j = list(map(int, input().split()))
    network[i].append(j)
    network[j].append(i)


from collections import deque


n = 0
s = []
queue = deque([1])
while n < N:
    top = queue.popleft()
    s.append(top)
    for i in network[top]:
        if i not in s:
            queue.append(i)
            if distance[i] > distance[top]+1:
                distance[i] = distance[top]+1
                res[i] = top

    n += 1


print("Yes")  
for r in res[2:]:
    print(r)

### FIXED CODE ###

import numpy as np

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

network = [[] for _ in range(N+1)]
res = [0 for _ in range(N+1)]
distance = [N+1 for _ in range(N+1)]
distance[1] = 0


for _ in range(M):
    i, j = map(int, input().split())
    network[i].append(j)
    network[j].append(i)


from collections import deque


n = 0
s = []
queue = deque([1])
while n < N:
    top = queue.popleft()
    for i in network[top]:
        if distance[i] > distance[top]+1:
            distance[i] = distance[top]+1
            res[i] = top
            queue.append(i)
    n += 1


print("Yes")  
for r in res[2:]:
    print(r)