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

import heapq

def dijkstra(adj, start, goal=None):
    n = len(adj)
    dist = [float("inf") for i in range(n)]
    prev = [float("inf") for i in range(n)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while len(q) != 0:
        prov_cost, src = heapq.heappop(q)

        if dist[src] < prov_cost:
            continue

        for dest in range(n):
            cost = adj[src][dest]
            if cost != float("inf") and dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost
                heapq.heappush(q, (dist[dest], dest))
                prev[dest] = src

    if goal is not None:
        return get_path(goal, prev)
    else:
        return dist

def get_path(goal, prev):
    path = [goal]
    dest = goal
    while prev[dest] != float("inf"):
        path.append(prev[dest])
        dest = prev[dest]
    return list(reversed(path))

n, m = map(int, input().split())
adj = [[float("inf") for i in range(n)] for i in range(n)]
path = []
for i in range(m):
    a, b, c = map(int, input().split())
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
    path.append(set([a - 1, b - 1]))
for i in range(n):
    for j in range(n):
        if i != j:
            saitan = dijkstra(adj, i, j)
            for k in range(len(saitan) - 1):
                ss = set(saitan[k:k + 2])
                if ss in path:
                    path.remove(ss)
print(len(path))

### FIXED CODE ###

import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
shortest = []
for i in range(n):
     shortest.append(dijkstra(adj, n, i))
ans = 0
for i in range(n):
    for cost, j in adj[i]:
        if cost > shortest[i][j]:
            ans += 1
print(ans // 2)
### BUGGY CODE ###

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

counter = 0

for x in range(k+1):
    if s-x > 2 * k:
        continue
    for y in range(k+1):
        if s-x-y > k:
            continue
        for z in range(k+1):
            if s == x+y+z:
                counter += 1
                break
                
print(counter)

### FIXED CODE ###

k,s = map(int,input().split())
counter = 0

for x in range(k+1):
    if s-x > 2*k:
        continue
    for y in range(k+1):
        if s-x-y > k or s-x-y < 0:
            continue
        else:
            counter += 1
            
print(counter)
### BUGGY CODE ###

import bisect

n = int(input())

d = {}
m = 1
for i in range(n):
    s = input()
    if s in d:
        d[s] += 1
        if m < d[s]:
            m = d[s]
    else:
        d[s] = 1

l = []
for i in d:
    if d[i] == m:
        bisect.insort_left(l, i)
        
for i in l:
    print(i)

### FIXED CODE ###

from collections import Counter

n = int(input())

l = [input() for i in range(n)]

c = Counter(l)

ml = c.most_common()
mc = ml[0][1]

ml.sort()

for i in ml:
    if i[1] == mc:
        print(i[0])
### BUGGY CODE ###

import math

INF = float("inf")

V, E = map(int, input().split())
es = []

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

d = [INF] * V
d[0] = 0

for _ in range(V - 1):
    updated = False
    for e in es:
        if math.isinf(d[e[0]]):
            continue
        if d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            updated = True
    if not updated:
        break

negative = [False] * V

for _ in range(V):
    for e in es:
        if math.isinf(d[e[0]]):
            continue
        if d[e[1]] > d[e[0]] + e[2]:
            negative[e[1]] = True
            d[e[1]] = d[e[0]] + e[2]
        elif negative[e[1]]:
            d[e[1]] = True
print(-d[V-1] if not negative[V-1] else "inf")


### FIXED CODE ###

import math

INF = float("inf")

V, E = map(int, input().split())
es = []

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

d = [INF] * V
d[0] = 0
cnt = [0] * V

for _ in range(V):
    updated = False
    for e in es:
        if math.isinf(d[e[0]]):
            continue
        if d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            cnt[e[1]] += 1
            updated = True
    if not updated:
        break

print(-d[V-1] if cnt[V-1] < V else "inf")
### BUGGY CODE ###

# -- coding:utf-8 --
n,m = map(int,input().split())
lr = [list(map(int,input().split())) for ii in range(m)]
L = [lr[jj][0] for jj in range(m) ]
R = [lr[jj][1] for jj in range(m) ]

count = 0

for nn in range(1,n+1):
    check = [0]*m
    for kk in range(m):
        if nn >= L[kk] and nn <= R[kk]:
            check[kk] = 1
        if sum(check) == m:
            count += 1

print(count)


### FIXED CODE ###

# -- coding:utf-8 --
n,m = map(int,input().split())
lr = [list(map(int,input().split())) for ii in range(m)]
L = [lr[jj][0] for jj in range(m) ]
R = [lr[jj][1] for jj in range(m) ]

if min(R)-max(L) < 0:
    print(0)
else:
    print(min(R)-max(L)+1)
### BUGGY CODE ###

a,b,c,k = (int(x) for x in input().split())
answer = 0
for i in range(k):
    if a>0:
        answer += 1
        a -= 1
    elif b > 0:
        b -= 1
    else:
        answer -= 1
        c -= 1
        pass
    pass
print(answer)

### FIXED CODE ###

a,b,c,k = (int(x) for x in input().split())
answer = 0
answer += min(a,k)
k = k - min(a,k)
k = k - min(b,k)
answer -= min(c,k)
print(answer)
### BUGGY CODE ###

import numpy as np

n, x, y = map(int, input().split())

ans = []
for i in range(1, n+1):
  for j in range(i, n+1):
    ji = i - j
    xi = i - x
    jy = y - j
    l = [np.abs(ji),  np.abs(xi) + 1 + np.abs(jy)]
    m = min(l)
    ans.append(m)
      
    
for k in range(n-1):
  print(ans.count(k+1))


### FIXED CODE ###

n, x, y = map(int, input().split())

ans = [0]*n
for i in range(1, n+1):
  for j in range(i, n+1):
    m = min(j-i,  abs(x-i) + 1 + abs(j-y))
    ans[m] += 1
      
print(*ans[1:], sep = '\n')
### BUGGY CODE ###

from sys import exit

H, W, M = map(int, input().split())

b = [[False] * W for _ in range(H)]
r = [0] * H
c = [0] * W
for _ in range(M):
    h, w = map(int, input().split())
    b[h-1][w-1] = True
    r[h-1] += 1
    c[w-1] += 1

list_r, list_c = [], []
max_r, max_c = max(r), max(c)

for i in range(H):
    if r[i] == max_r:
        list_r.append(i)

for i in range(W):
    if c[i] == max_c:
        list_c.append(i)

for v1 in list_r:
    for v2 in list_c:
        if not b[v1][v2]:
            print(max_r + max_c)
            exit()

print(max_r + max_c - 1)

### FIXED CODE ###

from sys import exit

H, W, M = map(int, input().split())

r = [0] * H
c = [0] * W
l = []
for _ in range(M):
    h, w = map(int, input().split())
    l.append([h-1, w-1])
    r[h-1] += 1
    c[w-1] += 1

set_r = set()
set_c = set()
max_r, max_c = max(r), max(c)

for i in range(H):
    if r[i] == max_r:
        set_r.add(i)

for i in range(W):
    if c[i] == max_c:
        set_c.add(i)

cnt = 0
for x, y in l:
    if x in set_r and y in set_c:
        cnt += 1

if cnt == len(set_r) * len(set_c):
    print(max_r + max_c - 1)
else:
    print(max_r + max_c)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    a1 = list(map(int,input().split()))
    a.append(a1)
l = [0 for i in range(n)]
l1 = [0 for i in range(n)]
day = 0
count1 = 0
count2 = 0
key = 1
b = n*(n-1)//2
while count1 < b:
    for i in range(n-1):
        if l[i] < n-1 and l1[i] == 0:
            j = a[i][l[i]] - 1
            if l1[j] == 0 and l[j] < n-1:
                if a[j][l[j]] == i + 1:
                    count1 += 1
                    l[i] += 1
                    l[j] += 1
                    l1[i] = 1
                    l1[j] = 1
    if count1 > count2:
        day += 1
        count2 = count1
        l1 = [0 for i in range(n)]
    else:
        key = 0
        break
if key == 1:
    print(day)
else:
    print(-1)

### FIXED CODE ###

from collections import deque
n = int(input())
a = []
for i in range(n):
    a1 = list(map(int,input().split()))
    a.append(a1)
l = [[[] for i in range(n)] for i in range(n)]
c = 0
day = 0
for i in range(n):
    ap = [i,a[i][0]-1]
    ap.sort()
    for j in range(1,n-1):
        p = [i,a[i][j]-1]
        p.sort()
        l[ap[0]][ap[1]].append(p)
        ap = p
rl = [[0 for i in range(n)] for i in range(n)]
dl = [[0 for i in range(n)] for i in range(n)]
d = deque()
for i in range(n):
    for j in range(n):
        if i < j:
            if len(l[i][j]) > 0:
                for k in l[i][j]:
                    rl[k[0]][k[1]] += 1
#print(rl)
for i in range(n):
    for j in range(n):
        if i < j:
            if rl[i][j] == 0:
                d.append([[i,j],0])
al = []
key = 0
#print(l)
if len(d) == 0:
    key = 1
while len(d):
    #print(d)
    now,day = d.pop()
    day += 1
    if len(l[now[0]][now[1]]) == 0:
        al.append(day)
    else:
        for i in l[now[0]][now[1]]:
            if rl[i[0]][i[1]] == 1:
                rl[i[0]][i[1]] -= 1
                d.append([i,max(day,dl[i[0]][i[1]])])
            else:
                rl[i[0]][i[1]] -= 1
                dl[i[0]][i[1]] = max(day,dl[i[0]][i[1]])
    if day > n*(n-1)//2:
        key = 1
        break
md = 0
for i in range(n):
    md += sum(rl[i])
if key == 1 or md > 0:
    print(-1)
else:
    print(max(al))
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10*5)

ans=0
r,g,b,n=map(int,input().split())
for i in range(n//r+2):
    for j in range(n//g+2):
        k=n-i*r-j*g
        if k>=0 and k%b==0:
            ans+=1

print(ans)

### FIXED CODE ###

ans=0
r,g,b,n=map(int,input().split())
for i in range(n//r+2):
    for j in range(n//g+2):
        k=n-i*r-j*g
        if k>=0 and k%b==0:
            ans+=1

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

arr = [0 for i in range(2019)]
arr[0] = 1

s = input()
n = len(s)

num = ""
for i in range(1,n+1):
    num = s[-i] + num
    arr[int(num)%2019] += 1


ans = 0
for m in arr:
    if m==0: continue
    ans += m*(m-1)//2

print(ans)



### FIXED CODE ###

arr = [0 for i in range(2019)]
arr[0] = 1

s = input()
n = len(s)

num = 0
for i,ele in enumerate(s[::-1]):
    num += int(ele) * pow(10, i, 2019)
    arr[num%2019] += 1


ans = 0
for m in arr:
    if m==0: continue
    ans += m*(m-1)//2

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

n, k = map(int, input().split())
if k == 1:
    print(0)
elif k == 2:
    if n % 2 == 0:
        print(0)
    else:
        print(1)
elif k == 3:
    if n%3 == 0:
        print(0)
    elif n%3 == 1:
        print(1)
    else:
        print(1)
elif k == 4:
    if n%4 == 0:
        print(0)
    elif n%4 == 1:
        print(1)
    elif n%4 == 2:
        print(2)
    else:
        print(1)
elif k == 5:
    if n%5 == 0:
        print(0)
    elif n%5 == 1:
        print(1)
    elif n%5 == 2:
        print(2)
    elif n%5 == 3:
        print(2)
    else:
        print(1)
else:
    while n > k:
        n = n-k
    if n < k-n:
        print(n)
    else:
        print(k-n)

### FIXED CODE ###

n, k = map(int, input().split())
if n < k:
    if n < k-n:
        print(n)
    else:
        print(k-n)
else:
    n = n%k
    if n < k-n:
        print(n)
    else:
        print(k-n)
### BUGGY CODE ###

N=int(input())
l1=[[] for i in range(N)]
for i in range(N):
    l=list(map(int,input().split()))
    for j in range(len(l)):
        l1[i].append(l[j])
pos=-1
f=-1
suma=0
for i in range(N):
    f=i
    if l1[i][0]>=l1[i][1] and l1[i][0]>=l1[i][2]:
        s=l1[i][0]
       # print(s)
        pos=0
    elif l1[i][1]>=l1[i][0] and l1[i][1]>=l1[i][2]:
        s=l1[i][1]
       # print(s)
        pos=1
    else:
        s=l1[i][2]
       # print(s)
        pos=2
    m=pos
    for j in range(i-1,-1,-1):
        if m==0:
            if l1[j][1]>=l1[j][2]:
                s=s+l1[j][1]
                #print(l1[j][1])
                m=1
            else:
                s=s+l1[j][2]
                #print(l1[j][2])
                m=2
        elif m==1:
            if l1[j][0]>=l1[j][2]:
                s=s+l1[j][0]
                #print(l1[j][0])
                m=0
            else:
                s=s+l1[j][2]
                #print(l1[j][2])
                m=2
        else:
            if l1[j][0]>=l1[j][1]:
                s=s+l1[j][0]
                #print(l1[j][0])
                m=0
            else:
                s=s+l1[j][1]
                #print(l1[j][1])
                m=1
    if suma<s:
        suma=s
    for j in range(i+1,N):
        if pos==0:
            if l1[j][1]>=l1[j][2]:
                s=s+l1[j][1]
                #print(l1[j][1])
                pos=1
            else:
                s=s+l1[j][2]
                #print(l1[j][2])
                pos=2
        elif pos==1:
            if l1[j][0]>=l1[j][2]:
                s=s+l1[j][0]
                #print(l1[j][0])
                pos=0
            else:
                s=s+l1[j][2]
                #print(l1[j][2])
                pos=2
        else:
            if l1[j][0]>=l1[j][1]:
                s=s+l1[j][0]
                #print(l1[j][0])
                pos=0
            else:
                s=s+l1[j][1]
                #print(l1[j][1])
                pos=1
    #print(s)
    if suma<s:
        suma=s
print(suma)


### FIXED CODE ###

N=int(input())
l1=[[] for i in range(N)]
for i in range(N):
    l=list(map(int,input().split()))
    for j in range(len(l)):
        l1[i].append(l[j])
l2=[[] for i in range(N)]
for j in l1[0]:
    l2[0].append(j)
for j in range(1,N):
    l2[j].append(l1[j][0]+max(l2[j-1][1],l2[j-1][2]))
    l2[j].append(l1[j][1]+max(l2[j-1][0],l2[j-1][2]))
    l2[j].append(l1[j][2]+max(l2[j-1][0],l2[j-1][1]))
#print(l2)
print(max(l2[N-1][0],l2[N-1][1],l2[N-1][2]))
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-I]+list(map(int,t[n:]))+[I]
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    z=[]
    for t in t[:n]:
        s,t,x=map(int,t.split())
        z.append((x,(bisect_left(d,s-x),bisect_left(d,t-x))))
    z.sort(reverse=1)
    for x,(l,r)in z:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

def main():
  ans = 0
  n = int(input())
  b = tuple(map(int, input().split()))
  b_ = tuple(set(b))
  ov = 10**9+7
  from fractions import gcd
  def lcm(a):
      x = a[0]
      ln = len(a)
      for i in range(1, ln):
          x = (x * a[i]) // gcd(x, a[i])
      return x
  l = lcm(b_)
  for i in b:
    ans += l//i%ov
  print(ans%ov)
if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  from functools import reduce
  from fractions import gcd
  ans = 0
  n = int(input())
  b = tuple(map(int, input().split()))
  ov = 10**9+7
  def lcm(x,y):
    return (x * y) // gcd(x, y)
  def lcm_list(a):
    return reduce(lcm, a, 1)
  l = lcm_list(b)
  for i in range(n):
    ans += l//b[i]
  print(ans%ov)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import sys

N, M, L = list(map(int, input().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
Q = int(input())
st = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

D = [[0] * N for _ in range(N)]
R = {}

for a, b, c in ABC:
  a -= 1
  b -= 1
  D[a][b] = c
  D[b][a] = c
  if a not in R:
    R[a] = [[b, c]]
  else:
    R[a].append([b, c])
  if b not in R:
    R[b] = [[a, c]]
  else:
    R[b].append([a, c])

inf = 10 ** 10
T = [[inf] * N for _ in range(N)]
import copy
for i in range(N):
  if i not in R: continue
  S = copy.deepcopy(R[i])
  T[i][i] = 0
  while S:
    t = S.pop()
    if t[1] <= L:
      if t[1] < T[i][t[0]]:
        T[i][t[0]] = t[1]
        for j in R[t[0]]:
          if t[1] + j[1] <= L:
            S.append([j[0], t[1] + j[1]])

for i in range(N):
  for j in range(N):
    if i == j:
      T[i][j] = 0
      continue
    if T[i][j] <= L:
      T[i][j] = 1
    else:
      T[i][j] = inf

for k in range(N):
  for i in range(N):
    for j in range(N):
      T[i][j] = min(T[i][j], T[i][k] + T[k][j])

for s, t in st:
  s -= 1
  t -= 1
  if T[s][t] == inf:
    print(-1)
  else:
    print(T[s][t] - 1)


### FIXED CODE ###

import sys

N, M, L = list(map(int, input().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
Q = int(input())
st = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

inf = 10 ** 10
D = [[inf] * N for _ in range(N)]
R = {}

for a, b, c in ABC:
  a -= 1
  b -= 1
  D[a][b] = c
  D[b][a] = c
  if a not in R:
    R[a] = [[b, c]]
  else:
    R[a].append([b, c])
  if b not in R:
    R[b] = [[a, c]]
  else:
    R[b].append([a, c])

for i in range(N):
  D[i][i] = 0

for k in range(N):
  for i in range(N):
    for j in range(N):
      D[i][j] = min(D[i][j], D[i][k] + D[k][j])


for i in range(N):
  for j in range(N):
    if i == j:
      D[i][j] = 0
      continue
    if D[i][j] <= L:
      D[i][j] = 1
    else:
      D[i][j] = inf

for k in range(N):
  for i in range(N):
    for j in range(N):
      D[i][j] = min(D[i][j], D[i][k] + D[k][j])

for s, t in st:
  s -= 1
  t -= 1
  if D[s][t] == inf:
    print(-1)
  else:
    print(D[s][t] - 1)
### BUGGY CODE ###

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

ans = 0
for i in range(N):
    if i!= N-1:
        for j in range(N-i-1):
            if (N-j-1)-i == A[i] + A[N-j-1]:
                ans += 1

print(ans)                

### FIXED CODE ###

# 二分探索モジュール bisect
# 添字はiとjの分で相殺(本当の添字は+1が必要だが[(i+1)-(j+1)]なのでいらない(以下は式変形))
import bisect
N = int(input())
A = list(map(int, input().split()))
X = [A[i]+i for i in range(N)]
Y = [j - A[j] for j in range(N)]
ans = 0
Y.sort()
for i in range(N):
    ans += bisect.bisect_right(Y,X[i]) - bisect.bisect_left(Y,X[i])
print(ans)


'''
bisect 二分探索モジュール
A = [1,1,3,3,3,4,5,6]
B = 3
bisect.bisect_left(A, b) 配列Aにbが左から何番目に入るかを返す #2
bisect.bisect_right(A,b) 配列Aにbが右から何晩目に入るかを返す #5
'''
### BUGGY CODE ###

import math
N=int(input())
Candidate=-(-math.sqrt(N)//1)
while N%Candidate!=0:
    Candidate+=1
print(len(str(Candidate))-2)

### FIXED CODE ###

import math
N=int(input())
Candidate=-(-math.sqrt(N)//1)
while N%Candidate!=0:
    Candidate-=1
Candidate=N/Candidate
print(len(str(Candidate))-2)
### BUGGY CODE ###

import numpy
N, M = map(int, input().split())
mat = [[0 for i in range(N)] for i in range(N)]
a = [0 for i in range(M)]
b = [0 for i in range(M)]
for i in range(M):
    st = input().split()
    a[i] = int(st[0])-1
    b[i] = int(st[1])-1
    mat[a[i]][b[i]]+=1
    mat[b[i]][a[i]]+=1

ans = 0
for n in range(M):
    mtx = numpy.array(mat)
    mtx[a[n],b[n]] -= 1
    mtx[b[n],a[n]] -= 1
    roopex = numpy.zeros([N, N])
    for i in range(N):
        for j in range(N):
            if mtx[i, j] != 0:
                roopex[i, j] = 1
    rootnum = numpy.dot(mtx, mtx)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if rootnum[i, j] != 0:
                    roopex[i, j] = 1
        rootnum = numpy.dot(rootnum, mtx)
    flag = 0
    for i in range(N):
        for j in range(N):
            if roopex[i, j] == 0:
                flag = 1
                break
        if flag == 1:
            break
    if flag == 1:
        ans += 1

print(ans)


### FIXED CODE ###

V, E = map(int, input().split())
a = [0 for i in range(E)]
b = [0 for i in range(E)]
m = [[0 for i in range(V)] for i in range(V)]
for i in range(E):
    a[i], b[i]=map(int, input().split())
    m[a[i]-1][b[i]-1]+=1
    m[b[i]-1][a[i]-1]+=1
S=0
for n in range(E):
    m[a[n]-1][b[n]-1]-=1
    m[b[n]-1][a[n]-1]-=1
    U=[[] for i in range(V)]
    for i in range(V):
        for j in range(V):
            if m[i][j]!=0:
                U[i].append(j)
    P=[set() for i in range(E+1)]
    P[0].add(0)
    Q=set()
    R=[False for i in range(V)]
    for i in range(1,E+1):
        for u in P[i-1]:
            for v in U[u]:
                if not(R[v]):
                    R[v]=True
                    P[i].add(v)
                    Q.add(v)
        if len(P[i])==0:
            break
    if len(Q)!=V:
        S+=1
    m[a[n]-1][b[n]-1]+=1
    m[b[n]-1][a[n]-1]+=1
print(S)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections

H,W = map(int, input().split())

b = [[True]*(W+2)]
for _ in range(H):
    b.append([True] + [x == '#' for x in input().strip()] + [True])
b.append([True]*(W+2))

q = collections.deque()
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            q.appendleft((i,j))
t = 0
while q:
    tmp = collections.deque()
    while q:
        i,j = q.pop()
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.appendleft((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.appendleft((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.appendleft((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.appendleft((i+1,j))
    q = tmp
    t += 1

print(t-1)


### FIXED CODE ###

import sys
input=sys.stdin.readline
H,W = map(int, input().split())

b = [[True]*(W+2)]
for _ in range(H):
    b.append([True] + [x == '#' for x in input().strip()] + [True])
b.append([True]*(W+2))

check = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            check.append((i,j))
t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

print(t-1)