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

N, M = map(int, input().split())
from collections import defaultdict

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 3 * N + 4
dist = [float("inf")] * cnt


que = [S]
dist[S] = 0
visited = [False] * cnt
visited[S] = True
while len(que) != 0:
    q = que.pop()
    for v in graph[q]:
        if v == q:
            continue
        if dist[v] > dist[q] + 1:
            dist[v] = dist[q] + 1
            visited[v] = True
            que.append(v)
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)


### FIXED CODE ###

import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = 3 * 10 ** 5 + 10
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

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

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

        return list(reversed(path))


N, M = map(int, input().split())
from collections import defaultdict

graph = defaultdict(dict)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u][v + N] = 1
    graph[u + N][v + 2 * N] = 1
    graph[u + 2 * N][v] = 1
S, T = map(int, input().split())
S -= 1
T -= 1
dj = Dijkstra(graph, S)

dist, _ = dj.execute()
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)
### BUGGY CODE ###

L, R = map(int, input().split())
modlist =[]
for i in range(L, R):
    for j in range(L+1,R+1):
        nummod = i * j % 2019
        modlist.append(nummod)
        if nummod == 0:
            break
print(min(modlist))


### FIXED CODE ###

L, R = map(int, input().split())
modlist =[]
for i in range(L, R):
    for j in range(L+1,R+1):
        nummod = i * j % 2019
        modlist.append(nummod)
        if nummod == 0:
            break
    if nummod == 0:
        break
print(min(modlist))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 10 ** 9 + 7

K = []
for a in A:
    L = list(format(a, 'b').zfill(61))
    M = list(int(s) for s in L)
    K.append(M)

cnt = []
for i in range(61):
    temp_1 = 0
    for j in range(N):
        if K[j][i] == 1:
            temp_1 += 1
    temp_0 = N - temp_1
    cnt.append(temp_0 * temp_1)
cnt.reverse()

ans = 0
for i in range(61):
    ans += (2 ** i) * cnt[i] % MOD

print(ans % MOD)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
MOD = 10 ** 9 + 7
ans = 0

for i in range(61):
    cnt = np.count_nonzero(A & 1)
    ans += (2 ** i) * cnt * (N - cnt)
    A >>= 1

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

from functools import lru_cache


n, tracks = list(map(int, input().split()))
loads = []
for _ in range(n):
    loads.append(int(input()))

# print(loads)
slices = []
min_load = [99999999999999]

@lru_cache()
def slicing(rest, s=0):
    if not rest:
        # slices.append(s+[(len(s) and s[-1][1], len(loads))])
        return sum(loads[s:])

    result = 99999999999999
    for s1 in range(s+1, len(loads)-rest+1):
        sub_total = sum(loads[s: s1])
        if sub_total <= result:
            result = min(result, max(sub_total, slicing(rest-1, s1)))
    return result


rs = slicing(tracks-1)
print(rs)
# print(slices)


# def load_count_max(load):
#     print(load, max(sum(loads[l[0]: l[1]]) for l in load))
    # return max(sum(loads[l[0]: l[1]]) for l in load)


# result = min(map(load_count_max, slices))
# print(result)



### FIXED CODE ###

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


def check(p):
    i = 0
    for j in range(k):
        s = 0
        while s + T[i] <= p:
            s += T[i]
            i += 1
            if i == n:
                return n
    return i


def solve():
    left = 0
    right = 100000 * 10000
    while right - left > 1:
        mid = (left + right) // 2
        v = check(mid)
        if v >= n:
            right = mid
        else:
            left = mid
    return right


T = []
for _ in range(n):
    T.append(int(input()))
ans = solve()
print(ans)
### BUGGY CODE ###

n = int(input())
seq = input().strip()
ans = 0
r = []
g = []
b = []
for i in range(len(seq)):
    if seq[i] == 'R':
        r.append(i)
    elif seq[i] == 'G':
        g.append(i)
    else:
        b.append(i)

for i, val in enumerate(seq[:-2]):
    for j, val in enumerate(seq[i+1:-1], i+1):
        if seq[i] == seq[j]:
            continue
        if seq[i] in ('R', 'G') and seq[j] in ('R', 'G'):
            arr = b
        elif seq[i] in ('R', 'B') and seq[j] in ('R', 'B'):
            arr = g
        else:
            arr = r

        for k in arr:
            if k > j and j-i != k -j:
                ans += 1
        # for k, val in enumerate(seq[j+1:], j+1):
        #     if seq[i] != seq[k] and seq[j] != seq[k] and j-i != k-j:
        #         ans +=1
print(ans)

### FIXED CODE ###

n = int(input())
seq = input().strip()
ans = 0
r = set()
g = set()
b = set()
for i in range(len(seq)):
    if seq[i] == 'R':
        r.add(i)
    elif seq[i] == 'G':
        g.add(i)
    else:
        b.add(i)

ans = len(r)*len(g)*len(b)
for i in r:
    for j in g:
        if (i+j) % 2 == 0 and ((i + j) //2) in b:
            ans -= 1
        if max(i,j) + (max(i,j) - min(i,j)) in b:
            ans -= 1
        if min(i,j) - (max(i,j) - min(i,j)) in b:
            ans -= 1
        
print(ans)
### BUGGY CODE ###

def main():
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = []
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.append([i,j])
                cnt += 1
    ans = 0
    while True:
        ans += 1
        q_ = []
        for _ in range(len(q)):
            b = q.pop(0)
            if b[0]>0:
                if S[b[0]-1][b[1]]=='.':
                    cnt += 1
                    S[b[0]-1][b[1]]='#'
                    q_.append([b[0]-1,b[1]])
                    if cnt==h*w:
                        print(ans)
                        return
            if b[0]<h-1:
                if S[b[0]+1][b[1]]=='.':
                    cnt += 1
                    S[b[0]+1][b[1]]='#'
                    q_.append([b[0]+1,b[1]])
                    if cnt==h*w:
                        print(ans)
                        return
            if b[1]>0:
                if S[b[0]][b[1]-1]=='.':
                    cnt+=1
                    S[b[0]][b[1]-1]='#'
                    q_.append([b[0],b[1]-1])
                    if cnt==h*w:
                        print(ans)
                        return
            if b[1]<w-1:
                if S[b[0]][b[1]+1]=='.':
                    cnt += 1
                    S[b[0]][b[1]+1]='#'
                    q_.append([b[0],b[1]+1])
                    if cnt==h*w:
                        print(ans)
                        return
        q = q_

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i,a in enumerate(S) for j,b in enumerate(a) if b=='#']
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

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

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input()[:-1] for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    line = [0]*(W+1)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # グループごと白チョコを数える
        white_chocolate = [ line.copy() for _ in range(group_number+1) ]
        for i in loop_W:
            for g in range(group_number+1):
                for j in group[g]:
                    if chocolate[j][i] == '1':
                        white_chocolate[g][i] += 1
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(white_chocolate)
        now = zeros.copy()
        for w in loop_W:
            for g in range(len(white_chocolate)):
                if white_chocolate[g][w] > K:
                    cut = INF
                    break
                else:
                    now[g] += white_chocolate[g][w]
                if now[g] + white_chocolate[g][w+1] > K:
                    cut += 1
                    now = zeros.copy()
                    break
            if cut == INF:
                break
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input()[:-1] for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(group)
        cnt = zeros.copy()
        w = 0
        while w < W:
            now = zeros.copy()
            for g in range(len(group)):
                for i in group[g]:
                    if chocolate[i][w] == '1':
                        now[g] += 1
                if now[g] > K:
                    cut = INF
                    break
                if cnt[g] + now[g] > K:
                    cut += 1
                    w -= 1
                    cnt = zeros.copy()
                    break
                cnt[g] += now[g]
            w += 1
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()
### BUGGY CODE ###

S = list(input())
T = list(input())

li = [["" for _ in range(len(S)+1)] for _ in range(len(T)+1)]

for s in range(1,len(S)+1):
    for t in range(1,len(T)+1):
        if S[s-1] == T[t-1]:
            if len(li[t-1][s]) == max(len(li[t-1][s]), len(li[t][s-1]), len(li[t-1][s-1])+1):
                li[t][s] = li[t-1][s]
            elif len(li[t][s-1]) == max(len(li[t-1][s]), len(li[t][s-1]), len(li[t-1][s-1])+1):
                li[t][s] = li[t][s-1]
            elif len(li[t-1][s-1])+1 == max(len(li[t-1][s]), len(li[t][s-1]), len(li[t-1][s-1])+1):
                li[t][s] = li[t-1][s-1] + S[s-1]

        else:
            if len(li[t-1][s]) == max(len(li[t-1][s]), len(li[t][s-1])):
                li[t][s] = li[t-1][s]
            elif len(li[t][s-1]) == max(len(li[t-1][s]), len(li[t][s-1])):
                li[t][s] = li[t][s-1]
            
print(li[t][s])

### FIXED CODE ###

S = list(input())
T = list(input())

li = [[0 for _ in range(len(S)+1)] for _ in range(len(T)+1)]

for s in range(1,len(S)+1):
    for t in range(1,len(T)+1):
        if S[s-1] == T[t-1]:
            li[t][s] = max(li[t-1][s], li[t][s-1], li[t-1][s-1]+1)
        else:
            li[t][s] = max(li[t-1][s],li[t][s-1])

s = len(S)
t = len(T)
ans = ""
while(s and t):
    if (S[s-1]==T[t-1]) and (li[t][s]-1==li[t-1][s-1]):
        ans = S[s-1]+ans
        s-=1
        t-=1
    elif li[t-1][s] >= li[t][s-1]:
        t-=1
    elif li[t-1][s] < li[t][s-1]:
        s-=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(N-1):
    while A[i] > A[i+1]:
        A[i + 1] = A[i + 1] + 1
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(1,N):
    if A[i-1] > A[i]:
        count += A[i-1] - A[i]
        A[i] = A[i - 1]
print(count)
### BUGGY CODE ###

from itertools import accumulate
N = int(input())
A = list(map(int,input().split()))
R = [0]+list(accumulate(A))
ans = 0
for i in range(N):
    for j in range(i+1,N+1):
        if R[j]-R[i] == 0:
            ans += 1
print(ans)

### FIXED CODE ###

from itertools import accumulate
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
R = [0]+list(accumulate(A))
C = sorted(list(Counter(R).values()))
C.reverse()
ans = 0
for c in C:
  if c == 1:
    break
  ans += c*(c-1)//2
print(ans)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
 
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7
 
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
 
 
def main():
    n = II()
    a = [0] + [II() for _ in range(n-1)]
    d = {}
    for i in range(1,n):
        if a[i] not in d:
            d[a[i]] = []
        d[a[i]].append(i+1)
    m = {}
    def f(i):
        if i not in d:
            return 0
        t = [f(c) for c in d[i]]
        t.sort()
        r = 0
        for c in t:
            if r < c:
                r = c
            r += 1
        return r
    return f(1)
 
 
print(main())

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n = II()
    a = [0] + [II() for _ in range(n-1)]
    d = collections.defaultdict(list)
    for i in range(1,n):
        d[a[i]].append(i+1)
    m = {}
    def f(i):
        if not d[i]:
            return 0
        t = collections.defaultdict(int)
        for c in d[i]:
            t[f(c)] += 1
        t = list(t.items())
        t.sort()
        r = 0
        for c, tc in t:
            if r < c:
                r = c
            r += tc
        return r
    return f(1)


print(main())
### BUGGY CODE ###

import sys
input=sys.stdin.readline

N=int(input())
p=list(map(float,input().split()))

dp=[[0]*(N+1)for _ in range(N+1)]
for i in range(N+1):
    for j in range(N+1):
        if i==0 and j==0:
            dp[i][j]=1
        elif i==0:
            continue
        elif j==0:
            dp[i][j]=dp[i-1][j]*(1-p[i-1])
        else:
            dp[i][j]=(dp[i-1][j]*(1-p[i-1]))+(dp[i-1][j-1]*p[i-1])

ans=0
for j in range(((N//2)+1),N+1):
    ans+=dp[N][j]
print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline

N=int(input())
p=list(map(float,input().split()))

dp=[[0]*(N+1)for _ in range(N+1)]
for i in range(N+1):
    for j in range(N+1):
        if i==0 and j==0:
            dp[i][j]=1
        elif j==0:
            dp[i][j]=dp[i-1][j]*(1-p[i-1])
        elif i>=j:
            dp[i][j]=(dp[i-1][j]*(1-p[i-1]))+(dp[i-1][j-1]*p[i-1])

ans=0
for j in range(((N//2)+1),N+1):
    ans+=dp[N][j]
print(ans)
### BUGGY CODE ###

t = input()
if t[0] == "?":
    t = "D" + t[1:]
for i in range(1, len(t)):
    if t[i] =="?":
        if t[i-1] == "D":
            t = t[:i] + "P" + t[i+1:]
        else:
            t = t[:i] + "D" + t[i+1:]

print(t)

### FIXED CODE ###

print(input().replace("?", "D"))
### BUGGY CODE ###

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

# dp[i][w]: i番目の荷物で重さwの状態であるときの最大価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

# 配るDPで考える
for nimotsu in range(N):
    # 行取得
    w_weight, w_val = map(int, input().split())
    
    for w in range(W+1):
        # 品物を選ぶとき (上限超えなければ)
        sum_ = w + w_weight
        if sum_ <= W :
            dp[nimotsu+1][sum_] = max(dp[nimotsu+1][sum_], dp[nimotsu][w] + w_val)
            
        # 品物を選ばないとき
        dp[nimotsu+1][w] = max(dp[nimotsu+1][w] ,dp[nimotsu][w])

print(dp[N][W])

### FIXED CODE ###

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

# dp[i][w]: i番目の荷物で重さwの状態であるときの最大価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

# 配るDPで考える
for nimotsu in range(N):
    # 行取得
    w_weight, w_val = map(int, input().split())
    
    for w in range(W+1):
        # 品物を選ぶとき (上限超えなければ)
        sum_ = w + w_weight
        if sum_ <= W :
            dp[nimotsu+1][sum_] = max(dp[nimotsu+1][sum_], dp[nimotsu][w] + w_val)
            
        # 品物を選ばないとき
        dp[nimotsu+1][w] = max(dp[nimotsu+1][w] ,dp[nimotsu][w])

print(dp[N][W])
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
for j in range(len(A)):
    remove = A.pop(j)
    print(max(A))
    A.insert(j, remove)


### FIXED CODE ###

N = int(input())
numbers = []
for i in range(N):
    numbers.append(int(input()))
ordered = sorted(numbers, reverse = True)

for j in range(len(numbers)):
    if numbers[j] == ordered[0]:
        print(ordered[1])
    else:
        print(ordered[0])
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = s[0]
for i in range(1, n):
  if s[i] != s[i-1]:
    ans += s[i]
print(len(ans))


### FIXED CODE ###

n = int(input())
s = list(input())
ans = s[0]
for i in range(1, n):
  if s[i] != s[i-1]:
    ans += s[i]
print(len(ans))
### BUGGY CODE ###

def my_code():
    n = int(input())
    a = list(map(int,input().split()))
    for i in range(1, n+1):
        print(a.count(i))

my_code()


### FIXED CODE ###

def my_code():
    n = int(input())
    a = [0]*n
    # a = list(map(int,input().split()))
    for i in list(map(int, input().split())):
        a[i-1] += 1
    print(*a,sep="\n")

my_code()
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
 
count=0
for i in range(0,N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      if L[i]+L[j]>L[k] and L[i]+L[k]>L[j] and L[j]+L[k]>L[i]:
        count+=1
print(count)

### FIXED CODE ###

import bisect
 
N=int(input())
L=list(map(int,input().split()))
 
L.sort()
count=0
for i in range(N):
  for j in range(i+1,N):
    c=L[i]+L[j]
    index=bisect.bisect_left(L,c)
    count+=max(0,index-j-1)
print(count)
### BUGGY CODE ###

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

Maxcounter = 0
for i in range(1,N):
    counter = 0
    k = i
    while k < N:
      if (A[k-1]>=A[k]):
        counter += 1
        k += 1
        if Maxcounter <= counter:
            Maxcounter = counter
      else:
        break
      
print(Maxcounter)


### FIXED CODE ###

N = int(input())
H = [int(x) for x in input().split()]

cnt = 0
maxcnt = 0
for j in range(0,N):
  if (j!=N-1)and(H[j]>=H[j+1]):
    cnt += 1
  else:
    if cnt>maxcnt:
      maxcnt = cnt
      cnt = 0
    else:
      cnt = 0
print(maxcnt)
### BUGGY CODE ###

N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = []
good_flags = [1 for _ in range(N)]

for _m in range(M):
    path = input().strip().split(' ')
    path = int(path[0]), int(path[1])
    # path = path if path[0] < path[1] else (path[1], path[0])
#    if path not in paths:

    p1, p2 = path if path[0] < path[1] else (path[1], path[0])
    if (p1, p2) in paths:
        continue

    if H[p1-1] > H[p2-1]:
        good_flags[p2-1] = 0
    elif H[p1-1] < H[p2-1]:
        good_flags[p1-1] = 0
    else:
        good_flags[p1-1] = 0
        good_flags[p2-1] = 0        

    paths.append(path) 

print(sum(good_flags))

### FIXED CODE ###

N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = []
max_neighbor = [ 0 for _ in range(N)]

for _m in range(M):
    path = input().strip().split(' ')
    path = int(path[0]), int(path[1])
    max_neighbor[path[0]-1] = max(max_neighbor[path[0]-1], H[path[1]-1])
    max_neighbor[path[1]-1] = max(max_neighbor[path[1]-1], H[path[0]-1])
count = 0
for n in range(N):
    if max_neighbor[n] < H[n]:
        count += 1
print(count)
### BUGGY CODE ###

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


L_list.sort()

res = 0


for i in range(len(L_list)):
        a= L_list[i]
        for j in range(i+1,len(L_list)):
                b= L_list[j]
                for k in range(j+1,len(L_list)):
                        c= L_list[k]

                        if c<a+b:
                                res+=1
                        else:
                                break

print(res)

### FIXED CODE ###

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

L_list.sort()
import bisect
res = 0
for i in range(N):
    a= L_list[i]
    for j in range(i+1,N):
        b= L_list[j]
        ind = bisect.bisect_left(L_list,a+b)
        res+=(ind-j-1)

print(res)
### BUGGY CODE ###

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

h,w = inm()
a = []
for i in range(h):
    a.append(list(ins()))
q = []
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
cnt = 0
#ddprint(a)
#ddprint(q)
while len(q)>0:
    qq = []
    while len(q)>0:
        i,j = q.pop()
        for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
            x = i+dx
            y = j+dy
            if 0<=x<h and 0<=y<w and a[x][y]=='.':
                a[x][y] = '#'
                qq.append((x,y))
    q = qq
    if len(q)>0:
        cnt += 1
    #ddprint(a)
    #ddprint(q)
print(cnt)


### FIXED CODE ###

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

h,w = inm()
a = []
for i in range(h):
    a.append(list(ins()))
q = []
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
cnt = 0
#ddprint(a)
#ddprint(q)
while len(q)>0:
    qq = []
    while len(q)>0:
        i,j = q.pop()
        for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
            x = i+dx
            y = j+dy
            if 0<=x<h and 0<=y<w and a[x][y]=='.':
                a[x][y] = '#'
                qq.append((x,y))
    q = qq
    if len(q)>0:
        cnt += 1
    #ddprint(a)
    #ddprint(q)
print(cnt)