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

#! /usr/bin/env python
# -*- coding: utf-8 -*-

if __name__ == '__main__':
    N, Q = map(int, input().split()) # N, Q for number
    sN = list(input())
    golems = []
    for i in range(0,N): # init golem
        golems.append({'loc': i})

    sQ = []
    remain = len(golems)
    for i in range(0, Q):
        t, d = input().split()
        sQ.append({'t': t, 'd': d})
    for q in sQ: # loop to handle Q
        for g in golems:
            if(g['loc'] >= 0 and sN[g['loc']] == q['t']):
                if(q['d'] == 'L'):
                    if(g['loc'] <= 0):
                        g['loc'] = -1
                        remain = remain - 1
                    else:
                        g['loc'] = g['loc'] - 1
                elif(q['d'] == 'R'):
                    if(g['loc'] >= N -1):
                        g['loc'] = -1
                        remain = remain - 1
                    else:
                        g['loc'] = g['loc'] + 1

    print(remain)

### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

sN = []
sQ = []
dQ = []
Q = 0
N = 0


def gor(pos):
    for i in range(Q):
        if sN[pos] == sQ[i]:
            if dQ[i] == 'R':
                pos = pos + 1
            else:
                pos = pos - 1

            if pos < 0:
                return False
            if pos > N - 1:
                return True

    return False


def getr():
    l = 0
    r = N - 1
    res = N
    while r >= l:
        mid = (l + r) // 2
        if gor(mid):
            res = mid
            r = mid - 1
        else:
            l = mid + 1
    return res


def gol(pos):
    for i in range(Q):
        if sN[pos] == sQ[i]:
            if dQ[i] == 'L':
                pos = pos - 1
            else:
                pos = pos + 1

            if pos > N - 1:
                return False
            if pos < 0:
                return True

    return False


def getl():
    l = 0
    r = N - 1
    res = -1
    while l <= r:
        mid = (l + r) // 2
        if gol(mid):
            res = mid
            l = mid + 1
        else:
            r = mid - 1
    return res


if __name__ == '__main__':
    N, Q = map(int, input().split())  # N, Q for number

    sN = input()  # squares

    for i in range(0, Q):
        t, d = input().split()
        sQ.append(t)
        dQ.append(d)
        #sQ.append({'t': t, 'd': d})

    removed_l = getl() + 1
    removed_r = N - getr()

    print(N - removed_l - removed_r)
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.readline

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)
mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))
CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
C,D = zip(*CD)
C = [min(c,mc) for c in C]

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,S,1)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
ans[1][S] = 0
while dq:
    t, w, v = heappop(dq)
    if ans[v][w] < t:
        continue
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            ans[nv][nw] = t + nt
            heappush(dq,(t+nt,nw,nv))

for i in range(2,N+1):
    print(min(ans[i]))





### FIXED CODE ###

from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.readline

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)

'''
from itertools import combinations 
N = 14
M = N*(N-1)//2
S = 0
UVAB = [[x,y,50,10**9] for x,y in combinations(range(1,N+1),2)] 
U,V,A,B = zip(*UVAB)
'''

mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))

CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
#CD = [[0,0]] + [[10**9,10**9] for i in range(N)]
C,D = zip(*CD)
C = [min(c,mc) for c in C]

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,S,1)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    t, w, v = heappop(dq)
    if ans[v][w] <= t:
        continue
    for i in range(w+1):
        ans[v][i] = min(t, ans[v][i])
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nw,nv))

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

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

ans_li = [i for i in range(a,b+1) if not a+k<=i<=b-k]
for ans in ans_li:
    print(ans)

### FIXED CODE ###

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

min_li = [i for i in range(a,min(a+k,b+1))]
max_li = [i for i in range(max(b-k+1,a),b+1)]

print('\n'.join(map(str,sorted(set(min_li+max_li)))))
### BUGGY CODE ###

n,m=map(int,input().split())
ans=[1 for i in range(n)]
for i in range(m):
	l,r=map(int,input().split())
	for j in range(n):
		if ans[j]==1:
			if j<l-1 or j>r-1:
				ans[j]=0
print(ans.count(1))

### FIXED CODE ###

n,m=map(int,input().split())
lmax,rmin=0,n
for i in range(m):
	l,r=map(int,input().split())
	if l>lmax:
		lmax=l
	if r<rmin:
		rmin=r
if rmin-lmax<0:
	print(0)
else:
	print(rmin-lmax+1)
### BUGGY CODE ###

N=int(input());tt=0
while(N):
    tt+=(N%10);N//=10
print("No" if tt%9 else "Yes")

### FIXED CODE ###

print("No"if int(input())%9 else "Yes")
### BUGGY CODE ###

n = int(input())
A = set(map(int, input().split()))

maxa = max(A)

if maxa%2 == 1:
    l2 = maxa//2
    r2 = maxa//2 + 1
else:
    l2 = maxa//2
    r2 = maxa//2

i = 0
while True:
    if l2-i in A:
        print(maxa, l2-i)
        break
    
    if r2+i in A:
        print(maxa, r2+i)
        break
    
    i += 1


### FIXED CODE ###

n = int(input())
A = map(int, input().split())
A = sorted(A)
maxa = max(A)

from bisect import bisect_left
m = (maxa+1)//2
l2 = bisect_left(A, m)

if abs(A[l2] - m) >= abs(A[l2-1] - m):
    print(maxa, A[l2-1])
else:
    print(maxa, A[l2])
### BUGGY CODE ###

n = int(input())
ss = input()

queue = []
for i in range(n-2):
    queue.append(('', i))

ans = 0
nn = n-3
memo = set()
while queue:
    s, pos = queue.pop()
    # print((s,pos))
    for i in range(pos, n):
        t = s + ss[i]
        if len(t) == n - nn:
            memo.add(t)
        else:
            queue.append((t,i+1))
print(len(memo))
# print(memo)


### FIXED CODE ###

from collections import Counter
from bisect import bisect_right

n = int(input())
s = input()
ndict = {str(i):[] for i in range(10)}
for i,c in enumerate(s):
    ndict[c].append(i)

ans = 0
for i in range(1000):
    PIN = str(i).zfill(3)
    idx = -1
    cc = ''
    for c in PIN:
        if ndict[c] == []:
            break
        tmp = bisect_right(ndict[c], idx)
        if tmp >= len(ndict[c]):
            break
        idx = ndict[c][tmp]
        cc = c
    else:        
        ans += 1
print(ans)
### BUGGY CODE ###

import fractions
n = int(input())
l = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()

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

mod = 10**9+7
a = 0
for i in range(n):
    a += ans//l[i]
    a %= mod
print(int(a%mod))


### FIXED CODE ###

import fractions
n = int(input())
l = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()

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

mod = 10**9+7
a = 0
for i in range(n):
    a += ans//l[i]
    
print(a%mod)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
if A == sorted(A) and len(A) == len(set(A)):
  print(1)
  exit(0)

def check(X):
  idx = [0]
  ltr = [0]
  for a in A:
    if idx[-1] < a:
      idx.append(a)
      ltr.append(0)
    else:
      while True:
        while idx[-1] > a:
          idx.pop()
          ltr.pop()
        if idx[-1] != a:
          idx.append(a)
          ltr.append(0)
        if idx[-1] == 0:
          return False
        ltr[-1] += 1
        if ltr[-1] < X:
          break
        a = idx[-1] - 1
        idx.pop()
        ltr.pop()
  return ltr[0] == 0

t = [0, N]
while t[1] - t[0] > 1:
  mid = (t[0] + t[1]) // 2
  t[check(mid)] = mid
print(t[1])


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
if A == sorted(A) and len(A) == len(set(A)):
  print(1)
  exit(0)

def check(X):
  idx = [0]
  ltr = [0]
  for a in A:
    if idx[-1] < a:
      idx.append(a)
      ltr.append(0)
    else:
      while True:
        while idx[-1] > a:
          idx.pop()
          ltr.pop()
        if idx[-1] != a:
          idx.append(a)
          ltr.append(0)
        if idx[-1] == 0:
          return False
        ltr[-1] += 1
        if ltr[-1] < X:
          break
        a = idx[-1] - 1
        idx.pop()
        ltr.pop()
  return ltr[0] == 0

t = [1, N]
while t[1] - t[0] > 1:
  mid = (t[0] + t[1]) // 2
  t[check(mid)] = mid
print(t[1])
### BUGGY CODE ###

from fractions import gcd
# def GCD(a: int, b: int) -> int:
#     return a if b == 0 else GCD(b, a % b)


class SegTree():
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.data = [ele_id] * (2 * self.n - 1)
        self.ele_id = ele_id
        self.operation_func = operation_func

    def __getitem__(self, idx):
        return self.data[idx + self.n - 1]

    def init(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n - 1] = data_init[i]
        for i in range(self.n - 2, -1, -1):
            self.data[i] = self.operation_func(self.data[2 * i + 1],
                                               self.data[2 * i + 2])

    def update(self, idx, x):
        # idx番目の要素をxに更新する
        idx += self.n - 1
        self.data[idx] = x
        while idx > 0:
            idx = (idx - 1) // 2
            self.data[idx] = self.operation_func(self.data[2 * idx + 1],
                                                 self.data[2 * idx + 2])

    def query(self, a, b):
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        # [a, b)の最小値を求める
        if r <= a or b <= l:
            # [a, b)が[l, r)と交差しない
            return self.ele_id

        if a <= l and r <= b:
            # [a, b)が[l, r)を完全に含む
            return self.data[k]
        else:
            # [a, b)と[l, r)は一部被る
            child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
            child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
            return self.operation_func(child_l, child_r)


n = int(input())
a = tuple(map(int, input().split()))
seg_gcd = SegTree(n, 0, gcd)
seg_gcd.init(a)

ans = seg_gcd.data[0]
for i in range(n):
    seg_gcd.update(i, 0)
    ans = max(ans, seg_gcd.data[0])
    seg_gcd.update(i, a[i])

print(ans)


### FIXED CODE ###

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

def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)

l = [0]
r = [0]
for i in range(n):
    l.append(GCD(l[i], a[i]))
    r.append(GCD(r[i], a[n-1 - i]))
r = r[::-1]

ans = 1
for i in range(n):
    ans = max(ans, GCD(l[i], r[i+1]))

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

n = int(input())

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


total = 0
for i in range(n-1):
    for j in a[i+1:]:
        total += (a[i]*j)
        total = total%(10**9+7)

print(total)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
 
ans = 0
total = sum(A)
for i in range(N - 1):
    total -= A[i]
    ans += (A[i] * total) 
 
print(ans % mod)
### BUGGY CODE ###

from copy import deepcopy

import numpy as np


H, W = map(int, input().split())
field = np.array([[c == "." for c in input()] for _ in range(H)], dtype=np.int16)

u = deepcopy(field)
d = deepcopy(field)
l = deepcopy(field)
r = deepcopy(field)

for i in range(H):
    for j in range(1, W):
        if field[i, j]:
            l[i, j] = l[i, j - 1] + 1
        if field[i, W - j - 1]:
            r[i, W - j - 1] = r[i, W - j] + 1

for j in range(W):
    for i in range(1, H):
        if field[i, j]:
            u[i, j] = u[i - 1, j] + 1
        if field[H - i - 1, j]:
            d[H - i - 1, j] = d[H - i, j] + 1

print((u + d + l + r - 3).max())



### FIXED CODE ###

import numpy as np


H, W = map(int, input().split())
field = [[c == "." for c in input()] for _ in range(H)]
field = np.array(field, dtype=np.int16)

u = field.copy()
d = field.copy()
l = field.copy()
r = field.copy()

for i in range(1, H):
    u[i] = (u[i - 1] + 1) * u[i]
    d[-i - 1] = (d[-i] + 1) * d[-i - 1]

for j in range(1, W):
    l[:, j] = (l[:, j - 1] + 1) * l[:, j]
    r[:, -j - 1] = (r[:, -j] + 1) * r[:, -j - 1]

print((u + d + l + r - 3).max())
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ch=[]
for i in range(n):
    ch.append((a[i],i))
ch.sort(reverse=True)
#print(ch)
dp=[[0]*(n+1) for _ in range(n+1)]
dp[1][1]=ch[0][0]*ch[0][1]
dp[1][0]=ch[0][0]*(n-1-ch[0][1])
for i in range(2,n+1):
    for j in range(i+1):
        if j>=1:
            dp[i][j]=max(dp[i][j],dp[i-1][j-1]+ch[i-1][0]*abs(ch[i-1][1]-j+1))
        if i-1>=j:
            dp[i][j]=max(dp[i][j],dp[i-1][j]+ch[i-1][0]*abs(n-i+j-ch[i-1][1]))
print(max(dp[n]))

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
ch=[]
for i in range(n):
    ch.append((a[i],i))
ch.sort(reverse=True)
#print(ch)
dp=[[0]*(n+1) for _ in range(n+1)]
dp[1][1]=ch[0][0]*ch[0][1]
dp[1][0]=ch[0][0]*(n-1-ch[0][1])
for i in range(2,n+1):
    for j in range(i+1):
        if j>=1:
            dp[i][j]=max(dp[i][j],dp[i-1][j-1]+ch[i-1][0]*abs(ch[i-1][1]-j+1))
        if i-1>=j:
            dp[i][j]=max(dp[i][j],dp[i-1][j]+ch[i-1][0]*abs(n-i+j-ch[i-1][1]))
print(max(dp[n]))
### BUGGY CODE ###

N, S = map(int,input().split())
A = [int(s) for s in input().split()]
DP = [[0 for j in range(S + 1)] for i in range(N + 1)]
mod = 998244353
DP[0][0] = 1

for i in range(N):
  for j in range(S + 1):
    DP[i + 1][j] += 2 * DP[i][j]
    if j + A[i] <= S:
      DP[i + 1][j + A[i]] += DP[i][j]
    DP[i + 1][j] %= mod

print(DP[N][S])

### FIXED CODE ###

N, S = map(int,input().split())
A = [int(s) for s in input().split()]
DP = [[0 for j in range(S + 1)] for i in range(N + 1)]
mod = 998244353
DP[0][0] = 1

for i in range(N):
  for j in range(S + 1):
    DP[i + 1][j] += 2 * DP[i][j]
    DP[i + 1][j] %= mod
    if j + A[i] <= S:
      DP[i + 1][j + A[i]] += DP[i][j]
      DP[i + 1][j + A[i]] %= mod

print(DP[N][S])
### BUGGY CODE ###


# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
h,w = [int(i) for i in readline().split()]

a = [[int(i) for i in readline().split()] for _ in range(h)]
b = [[int(i) for i in readline().split()] for _ in range(h)]


dp = [set() for _ in range(w)]
dp[0] = set([0])

#print(dp)
for i in range(h):
    ndp = [set() for _ in range(w)]
    for j in range(w):
        v = a[i][j] - b[i][j]
        #print(v)
        for c in dp[j]:
            ndp[j].add(abs(c+v))
            ndp[j].add(abs(c-v))
        if j:
            for c in ndp[j-1]:
                ndp[j].add(abs(c+v))
                ndp[j].add(abs(c-v))

    dp = ndp
    #print(dp)
    

print(min(dp[j]))














### FIXED CODE ###


# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
h,w = [int(i) for i in readline().split()]

a = [[int(i) for i in readline().split()] for _ in range(h)]
b = [[int(i) for i in readline().split()] for _ in range(h)]


dp = [[0] for _ in range(w)]
dp[0][0] = 1

#print(dp)
N = 6401
for i in range(h):
    ndp = [[0]*N for _ in range(w)]
    for j in range(w):
        v = abs(a[i][j] - b[i][j])
        #print(v)
        for ii,c in enumerate(dp[j]):
            if ii+v < N:
                ndp[j][abs(ii+v)] |= c
            ndp[j][abs(ii-v)] |= c
        if j:
            for ii,c in enumerate(ndp[j-1]):
                if ii+v < N:
                    ndp[j][abs(ii+v)] |= c
                ndp[j][abs(ii-v)] |= c

    dp = ndp
    #print(dp)
    
c = [i for i,c in enumerate(dp[j]) if c]

#print(c)
print(min(c))
### BUGGY CODE ###

n = int(input())

import math
a = int(math.sqrt(n))

for i in range(a,n+1):
  if n%i == 0:
    move = (i-1) + int(n/i)-1
    print(move)
    exit()

### FIXED CODE ###

n = int(input())

import math
a = int(math.sqrt(n))

point = 1
for i in range(1,a+1):
  if n%i == 0:
    point = i
    
distance = (point-1) + int(n/point)-1
print(distance)
### BUGGY CODE ###

S = input()
C = 10**9+7


def answer(a):
    if a == '0' or a == '':
        return 1
    if a == '1':
        return 3
    b = '{:b}'.format(int(a[1:], 2))
    return (pow(3, (len(a)-1), C)+2*answer(b)) % C


print(answer(S))

### FIXED CODE ###

S = input()
C = 10**9+7
T = S[::-1]
N = len(S)
dp = [0]*N
dp[0] = 1+2*(int(T[0]))

for i in range(1, N):
    if T[i] == '0':
        dp[i] = dp[i-1]
    else:
        dp[i] = (pow(3, i, C)+2*dp[i-1]) % C
print(dp[-1])
### BUGGY CODE ###

from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
cnt = 0
hist = [0 for _ in range(N)]
for i in range(N-1,0,-1):
    if hist[i]==0:
        a = A[i]
        k = 0
        while 2**k<=a:
            k += 1
        b = 2**k-a
        ind = bisect_left(A,b)
        if ind<i and A[ind]==b and hist[ind]==0:
            hist[i]=1
            hist[ind]=1
            cnt += 1
        elif ind<i and A[ind]==b and hist[ind]==1:
            ind += 1
            while A[ind]==b and ind<i:
                if hist[ind]==0:
                    hist[i]=1
                    hist[ind]=1
                    cnt += 1
                    break
                ind += 1
print(cnt)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
A = [[A[i],0] for i in range(N)]
cnt = 0
for i in range(N-1,0,-1):
    if A[i][1]==0:
        a = A[i][0]
        A[i][1]=1
        k = 0
        while 2**k<=a:
            k += 1
        b = 2**k-a
        ind = bisect_left(A,[b,1])
        ind -= 1
        if ind<i and A[ind]==[b,0]:
            A[ind][1]=1
            cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(5000)
def max(a,b):
    if a >= b:
        return a
    return b
def min(a,b):
    if a <= b:
        return a
    return b

def main():

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

    dp = [[-1]*(n+1) for i in range(n)]
    def rec(i=0, j=n):
        if i == j:
            return 0
        if dp[i][j] != -1:
            return dp[i][j]
        # 太郎
        if (n - (j-i))%2==0:
            dp[i][j] = max(a[i] + rec(i+1,j), a[j-1] +rec(i,j-1))
        else:
            dp[i][j] = min(-a[i] + rec(i+1,j), -a[j-1] +rec(i,j-1))
        return dp[i][j]
    print(rec())

main()

### FIXED CODE ###

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

dp = [[0]*(n+1) for i in range(n+1)]
for l in range(1,n+1):
    for i in range(n+1-l):
        j = i+l
        if (n-l)%2 == 0:
            dp[i][j] = max(dp[i+1][j]+a[i], dp[i][j-1]+a[j-1])
        else:
            dp[i][j] = min(dp[i+1][j]-a[i], dp[i][j-1]-a[j-1])
print(dp[0][-1])
### BUGGY CODE ###

import itertools 
n = int(input())
a = list(map(int, input().split()))
a_list = [[j, i] for i, j in enumerate(a)]
#a_list.sort(reverse=True)
pairs = list(itertools.combinations(a_list, 2))
#print(pairs)
ans = 0
for pair in pairs:
    if pair[0][0] + pair[1][0] >= n:
        continue
    elif pair[0][1] == pair[1][1]:
        continue
    elif abs(pair[0][1]-pair[1][1]) == (pair[0][0]+pair[1][0]):
        ans += 1

"""
pairs = list(itertools.combinations(range(n), 2))
print(pairs)
ans = 0
for pair in pairs:
    if abs(pair[0]-pair[1]) == (a[pair[0]]+a[pair[1]]):
        ans += 1
"""

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
add_dic = {}
sub_dic = {}

for i in range(n):
    add_tmp = i + a[i]
    sub_tmp = i - a[i]
    if not add_tmp in add_dic.keys():
        add_dic[add_tmp] = 1
    else:
        add_dic[add_tmp] += 1
    if not sub_tmp in sub_dic.keys():
        sub_dic[sub_tmp] = 1
    else:
        sub_dic[sub_tmp] += 1

ans = 0
for k, v in add_dic.items():
    if k in sub_dic.keys():
        ans += v * sub_dic[k]
print(ans)
### BUGGY CODE ###

from collections import deque

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

G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

ls = deque([[0, 0]])
ans = [-1] * N
depthes = [float("inf")] * N 
ans[0] = 0
depthes[0] = 0
while len(ls) > 0:
    v, depth = ls.pop()

    for next_v in G[v]:
        if depthes[next_v] <= depth+1:
            continue
        ans[next_v] = v
        depthes[next_v] = depth + 1
        ls.append([next_v, depth+1])

if -1 in ans:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(ans[i]+1)

### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())
g = [[int(i) for i in input().split()] for j in range(M)]

G = [[] for i in range(N)]
for i in range(M):
    a, b = g[i]
    G[a-1].append(b-1)
    G[b-1].append(a-1)

marks = [-1 for i in range(N)]
node = deque([[0, 0]])
while len(node) > 0:
    v = node.popleft()
    if marks[v[0]] == -1:
        marks[v[0]] = v[1]
        for i in G[v[0]]:
            if marks[i] == -1:
                node.append([i, v[0]])

if -1 not in marks:
    print("Yes")
    for i in range(1, N):
        print(marks[i]+1)
else:
    print("No")
### BUGGY CODE ###

from collections import deque
import sys
from collections import defaultdict
import copy
# input = sys.stdin.readline



H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
gone = [[0] * W for _ in range(H)]
cot = 0
que = deque()

que_count = 0
for h in range(H):
    for w in range(W):
        if C[h][w] == "#":
            gone[h][w] = 1
            que.append((h,w))
            que_count += 1
            cot += 1
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans  = 0
nq = 0
while cot != H*W:
    while que_count != 0 and cot != H*W:
        h,w = que.popleft()
        que_count -= 1
        for temp in go:
            # この時，実際に行くのかは不明
            gx,gy = temp
            nx = w + gx
            ny = h + gy

            if 0<= nx < W and 0<= ny < H and gone[ny][nx] != 1: #行って無かったら，行く
                # この時に実際に移動する
                gone[ny][nx] = 1
                que.append( (ny,nx))
                nq += 1
                cot += 1
    que_count = nq

    ans += 1
print(ans)





### FIXED CODE ###

from collections import deque
import sys
from collections import defaultdict
import copy
# input = sys.stdin.readline



H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
gone = [[0] * W for _ in range(H)]
cot = 0
que = deque()

que_count = 0
for h in range(H):
    for w in range(W):
        if C[h][w] == "#":
            gone[h][w] = 1
            que.append((h,w))
            que_count += 1
            cot += 1
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans  = 0
nq = 0
while cot != H*W:
    while que_count != 0 and cot != H*W:
        h,w = que.popleft()
        que_count -= 1

        for temp in go:
            # この時，実際に行くのかは不明
            gx,gy = temp
            nx = w + gx
            ny = h + gy

            if 0<= nx < W and 0<= ny < H and gone[ny][nx] != 1: #行って無かったら，行く
                # この時に実際に移動する
                gone[ny][nx] = 1
                que.append( (ny,nx))
                nq += 1
                cot += 1
    que_count = nq
    nq = 0
    ans += 1
print(ans)