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

# _*_ coding:utf-8 _*_
#  CADDi2018 for Beginners C
#  https://atcoder.jp/contests/caddi2018b/tasks/caddi2018b_c

def getMaxGCD(count,product):
	maxPossibleInt = int(float(product)**(1.0/float(count)))
	checkGCDRange = range(maxPossibleInt+1,0,-1)
	maxGCD = maxPossibleInt+1
	for i in checkGCDRange:
		powNumber = i**count
		amari = product % powNumber
		if amari == 0:
			maxGCD = i
			break

	return maxGCD

if __name__ == '__main__':
	n , p  = map(int,input().strip().split(' '))
	if n == 1:
		print(p)
		exit(0)
	if p == 1:
		print(1)
		exit(0)
	solution=getMaxGCD(n,p)
	print('{}'.format(solution))

### FIXED CODE ###

# _*_ coding:utf-8 _*_
#  CADDi2018 for Beginners C
#  https://atcoder.jp/contests/caddi2018b/tasks/caddi2018_a

def getMaxGCD(count,product):
	# getPrimeFunction
	primeSet = []  # リストの初期化
	maxCheckNumber = round(product ** (1 / 2))
	checkRange = range(2, maxCheckNumber + 1, 1)
	for i in checkRange:
		baseCount = 0
		while product % i == 0:
			baseCount = baseCount + 1
			product = product // i
		if  0 < baseCount:
			primeSet.append((i, baseCount))
# 二つを引数にしそれぞれ出力する
	if 1 < product:
		primeSet.append((product, 1))

	gcdNumber = 1
	for baseCount,powNumber in  primeSet:
		gcdNumber = gcdNumber * (baseCount ** ( powNumber // count))
	return gcdNumber

if __name__ == '__main__':
	n , p  = map(int,input().strip().split(' '))
	if n == 1:
		print(p)
		exit(0)
	if p == 1:
		print(1)
		exit(0)
	solution=getMaxGCD(n,p)
	print('{}'.format(solution))
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
c = []
c.append(['×' for _ in range(w+2)])
for _ in range(h):
	c.append(list('×'+input()+'×'))
c.append(['×' for _ in range(w+2)])
ans = [[101 for _ in range(w+2)]for _ in range(h+2)]
if c[1][1] == '.':
	ans[1][1] = 0
else:
	ans[1][1] = 1

q = deque()

def bfs(x,y):
	global q
	global c
	q.append([x,y])

	while q:
		x,y = q.popleft()

		if [x,y] == [w,h]:
			return ans[h][w]
		if c[y][x+1] == '.':
			q.append([x+1,y])
			ans[y][x+1] = min(ans[y][x+1],ans[y][x])
		elif c[y][x+1] == '#':
			q.append([x+1,y])
			ans[y][x+1] = min(ans[y][x+1],ans[y][x]+1)
		if c[y+1][x] == '.':
			q.append([x,y+1])
			ans[y+1][x] = min(ans[y+1][x],ans[y][x])
		elif c[y+1][x] == '#':
			q.append([x,y+1])
			ans[y+1][x] = min(ans[y+1][x],ans[y][x]+1)


print(bfs(1,1))


### FIXED CODE ###

h,w = map(int,input().split())

s = []
for _ in range(h):
	s.append(list(input()))

inf = float('inf')
dp = [[inf for _ in range(w)] for _ in range(h)]
dp[0][0] = 0

for i in range(h):
	for j in range(w):
		if s[i][j] == ".":
			if j > 0 and i > 0:
				dp[i][j] = min(dp[i-1][j],dp[i][j-1])
			elif j > 0 and i == 0:
				dp[i][j] = dp[i][j-1]
			elif j == 0 and i > 0:
				dp[i][j] = dp[i-1][j]
		else:
			tmp1 = inf
			tmp2 = inf
			if i > 0:
				tmp1 = dp[i-1][j]
				if s[i-1][j] == ".":
					tmp1 += 1
			if j > 0:
				tmp2 = dp[i][j-1]
				if s[i][j-1] == ".":
					tmp2 += 1
			dp[i][j] = min(tmp1,tmp2)
			if i==0 and j==0:
				dp[i][j] = 1

print(dp[h-1][w-1])
### BUGGY CODE ###

import copy

N, K = map(int, input().split())
A = list(map(int, input().split()))
cnt = 1
S = []
S.append(A)

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

for i in range(N-K):
    B = copy.deepcopy(A)
    B[i:i+K] = sorted(B[i:i+K])
    S.append(B)

print(len(get_unique_list(S)))

### FIXED CODE ###

n,k=map(int,input().split())
P=[int(i) for i in input().split()]
import collections
from collections import deque
M1,M2=deque(),deque()
A1,A2=[],[]
M1.append(0)
for i in range(1,n):
  while M1:
    if P[M1[-1]]>P[i]:
      M1.pop()
    else:
      M1.append(i)
      break
  if not M1:
    M1.append(i)
  if M1[0]==i-k-1:
    M1.popleft()
  if i<k:
    continue
  else:
    A1.append(P[M1[0]])
M2.append(0)
for i in range(1,n):
  while M2:
    if P[M2[-1]]<P[i]:
      M2.pop()
    else:
      M2.append(i)
      break
  if not M2:
    M2.append(i)
  if M2[0]==i-k-1:
    M2.popleft()
  if i<k:
    continue
  else:
    A2.append(P[M2[0]])
ans=1
for i in range(n-k):
  if A1[i]==P[i] and A2[i]==P[i+k]:
    continue
  else:
    ans+=1
Q=[0]*n
for i in range(1,n):
  if P[i]>P[i-1]:
    Q[i]=Q[i-1]+1
  else:
    continue
count=0
for i in range(n):
  if Q[i]==k-1:
    count+=1
print(ans-max(0,count-1))
### BUGGY CODE ###

n,m = map(int,input().split())
diff = abs(n-m)
count1 = 1
count2 = 1
def saiki(n):
    if n<=1:
        return 1
    return n * saiki(n-1)
if diff >= 2:
    print(0)
elif diff == 1:
    #print((saiki(max(n,m))*saiki(min(n,m)))%(10**9+7))
    for i in range(1,max(n,m)+1):
        count1 *= i%(10**9+7)
    for i in range(1,(min(n,m)+1)):
        count2 *= i%(10**9+7)
    print(count1*count2)
else:
    #print((saiki(n)*saiki(m)*2)%(10**9+7))
    for i in range(1,n+1):
        count1 *= i%(10**9+7)
    print(count1*count1*2)


### FIXED CODE ###

import math
n,m = map(int,input().split())
diff = abs(n-m)
count1 = 1
count2 = 1
a = 1

if diff >= 2:
    print(0)
elif diff == 1:
    ans = math.factorial(max(n,m))
    print(ans*(ans//max(n,m))%(10**9+7))
else:
    ans = math.factorial(n)
    print(ans*ans*2%(10**9+7))
### BUGGY CODE ###

N = int(input())
dict1 = {}
for _ in range(N):
  s = input()
  if s in dict1:
    dict1[s] += 1
  else:
    dict1[s] = 1
list1 = [d[0] for d in dict1.items() if d[1]==max(dict1.values())]
list1.sort()
for s in list1:
  print(s)


### FIXED CODE ###

N = int(input())
dict1 = {}
for _ in range(N):
  s = input()
  if s in dict1:
    dict1[s] += 1
  else:
    dict1[s] = 1
max_num= max(dict1.values())
list1 = [d[0] for d in dict1.items() if d[1]==max_num]
list1.sort()
for s in list1:
  print(s)
### BUGGY CODE ###

K, S = map(int, raw_input().split())
cnt = 0
for i in range(0, K+1):
	for j in range(0, K+1):
		for k in range(0, K+1):
			if i + j + k == S:
				cnt += 1
				break

print cnt

### FIXED CODE ###

K, S = map(int, raw_input().split())
cnt = 0
for i in range(0, K+1):
	if S - i <= 2*K:
		for j in range(0, K+1):
			if 0 <= S - i - j and S - i - j <= K:
				cnt+=1
print cnt
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n,u,v = map(int,input().split())

    edges = [[] for _ in range(n)]

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

    stack1 = [u-1]
    stack2 = [v-1]

    dis1 = [-1] * n
    dis2 = [-1] * n
    dis1[u-1] = 0
    dis2[v-1] = 0

    count = 0

    while stack1 or stack2:
        count += 1
        for _ in range(len(stack1)):
            q1 = stack1.pop(0)
            for i in edges[q1]:
                if dis1[i] == -1 and dis2[i] == -1:
                    dis1[i] = count
                    stack1.append(i)

        for _ in range(len(stack2)):
            q2 = stack2.pop(0)
            for i in edges[q2]:
                if dis2[i] == -1:
                    dis2[i] = count
                    stack2.append(i)

    ans = 0
    for i in range(n):
        if dis1[i] != -1:
            ans = max(ans, dis2[i])

    print(ans-1)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,u,v = map(int,input().split())
edges = [[] for _ in range(n)]

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

visit1 = [False] * n
visit2 = [False] * n
visit1[u-1] = True
visit2[v-1] = True

dis1 = [-1] * n
dis2 = [-1] * n
dis1[u-1] = 0
dis2[v-1] = 0

stack1 = [u-1]
stack2 = [v-1]

while stack1:
    l = stack1.pop(-1)
    for i in edges[l]:
        if visit1[i] == False:
            visit1[i] = True
            dis1[i] = dis1[l] + 1
            stack1.append(i)

while stack2:
    l = stack2.pop(-1)
    for i in edges[l]:
        if visit2[i] == False:
            visit2[i] = True
            dis2[i] = dis2[l] + 1
            stack2.append(i)

ans = 0

for i in range(n):
    if dis1[i] < dis2[i]:
        ans = max(ans, dis2[i])

print(ans-1)
### BUGGY CODE ###

import sys
def IL(): return map(int,sys.stdin.readline().rstrip().split())

if __name__=='__main__':
    n,k = IL()
    a = list(IL())
    l = n-k+1
    pre = b = 0
    for i in range(l):
        result = 1
        for rep in a[i:i+k]:
            result = result*rep
        pre = b
        b = result
        if 0<i:
            if pre<b:
                print('Yes')
            else:
                print('No')
    exit()

### FIXED CODE ###

import sys
def IL(): return map(int,sys.stdin.readline().rstrip().split())

if __name__=='__main__':
    n,k = IL()
    a = list(IL())
    l = n-k
    pre = b = 0
    for i in range(l):
        if a[i]<a[i+k]:
            print('Yes')
        else:
            print('No')
    exit()
### BUGGY CODE ###

H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

import heapq
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
INF = float('inf')

dists = [[[INF]*4 for _ in range(W)] for _ in range(H)]
dists[r1][c1][0] = 0
hq = [(0,(r1*W+c1)*4)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    p,d = divmod(v,4)
    y,x = divmod(p,W)
    if y==r2 and x==c2:
        print(0--c//K)
        exit()
    for di,(dx,dy) in enumerate(dxy):
        if di != d:
            nc = c + (K-c)%K
            if dists[y][x][di] <= nc: continue
            dists[y][x][di] = nc
            heapq.heappush(hq, (nc,p*4+di))
        else:
            nx,ny = x+dx,y+dy
            if not 0 <= nx < W: continue
            if not 0 <= ny < H: continue
            if C[ny][nx] == '@': continue
            if dists[ny][nx][di] <= c+1: continue
            heapq.heappush(hq, (c+1,(ny*W+nx)*4+di))
print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x]: break
                if dists[ny][nx] <= dists[y][x] + 1: continue
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()
### BUGGY CODE ###

"""
Nは10**5以下。O(N)なら通る
"""

N = int(input())
A = []
B = []
for i in range(N):
    s = list(map(int, input().split()))
    A.append(s[0])
    B.append(s[1])

count = 0
for i in reversed(range(N)):
    if A[i] % B[i] == 0:
        continue
    else:
        s = B[i] - (A[i] % B[i])
        A[:i+1] = map(lambda x: x + s, A[:i+1])
        count += s

print(count)

### FIXED CODE ###

"""
Nは10**5以下。O(N)なら通る
"""

N = int(input())
A = []
B = []
for i in range(N):
    s = list(map(int, input().split()))
    A.append(s[0])
    B.append(s[1])

count = 0
for i in reversed(range(N)):
    if (count + A[i]) % B[i] == 0:
        continue
    else:
        s = B[i] - (count + A[i]) % B[i]
        count += s

print(count)
### BUGGY CODE ###

import itertools
MOD = 1000000007

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

answer = 0
comb_list = list(itertools.combinations(A, 2))
for c in comb_list :
    answer += int(c[0]) * int(c[1]) 
print (answer % MOD)

### FIXED CODE ###

MOD = 1000000007

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

answer = 0
s = sum(A)

for a in A:
    s -=a
    answer += (a * s)
print(answer%MOD)
### BUGGY CODE ###

import bisect

N, M = map(int, input().split())
PY = []
array = [[] for _ in range(N)]

for _ in range(M):
    P, Y = map(int, input().split())
    PY.append([P, Y])
    array[P-1].append(Y)

for p, y in PY:
    n = bisect.bisect_left(sorted(array[p-1]), y) + 1
    print('%06d%06d' % (p, n))


### FIXED CODE ###

import bisect

N, M = map(int, input().split())
PY = []
array = [[] for _ in range(N)]

for _ in range(M):
    P, Y = map(int, input().split())
    PY.append([P, Y])
    array[P-1].append(Y)
    
for i in range(N):
    array[i].sort()

for p, y in PY:
    n = bisect.bisect_left(array[p-1], y) + 1
    print('%06d%06d' % (p, n))
### BUGGY CODE ###

def is_good_grid():
    for r in range(n):
        for c in range(r):
            if t[r][c] != t[c][r]:
                return False
    return True


n = int(input())
s = tuple(input() for _ in range(n))

# (0,0)==(1,1)==...==(n-1,n-1)
# colのオフセットだけ変化させる
# それぞれのループで、n個の状態(0,k)==(1,k+1)==...を扱う

ans = 0
for k in range(n):
    t = [[''] * n for _ in range(n)]
    for r in range(n):
        for c in range(n):
            t[r][c] = s[r][(c + k) % n]
    if is_good_grid():
        ans += n
print(ans)


### FIXED CODE ###

N = int(input())
s = [input() for _ in range(N)]

ans = 0
a = 0
for b in range(N):
    if all(s[(i - a) % N][(j - b) % N] == s[(j - a) % N][(i - b) % N] for i in range(N) for j in range(i + 1, N)):
        ans += N
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(x) for x in input().split()]
ans =[]
mm=1
for i in range(n):
  for j in range(n):
    if mm==a[j]:
      ans.append(j+1)
      mm+=1
      break
print(*ans)

### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().split()]
vl =[]
tmp =[]
ans=[0]*n
for i,value in enumerate(a):
  tmp.append(i)
  vl.append(value)
for i in range(n):
  ans[vl[i]-1]=tmp[i]+1
print(*ans)
### BUGGY CODE ###

s = input()
n = len(s)
k = n if n % 2 == 0 else n + 1
ans = [0] * n
for i in range(n):
    p = i
    for _ in range(k):
        if s[p] == 'R':
            p += 1
        else:
            p -= 1
    ans[p] += 1
print(' '.join([str(x) for x in ans]))

### FIXED CODE ###

import math
s = input()
n = len(s)
ans = [0] * n
i = 0
while i < n:
    r = 0
    while s[i] == 'R':
        r += 1
        i += 1
    ans[i-1] += math.ceil(r / 2)
    ans[i] += math.floor(r / 2)
    l = 0
    while i < n and s[i] == 'L':
        l += 1
        i += 1
    ans[i-l-1] += math.floor(l / 2)
    ans[i-l] += math.ceil(l / 2)
print(' '.join([str(x) for x in ans]))
### BUGGY CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())

    edges = defaultdict(deque)
    deg = defaultdict(int)

    for i in range(1, N + 1):
        A = list(map(int, input().split()))
        for j in range(N - 2):
            edges[(min(i, A[j]), max(i, A[j]))].append((min(i, A[j + 1]), max(i, A[j + 1])))
            deg[(min(i, A[j + 1]), max(i, A[j + 1]))] += 1

    que = deque()
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            if deg[(i, j)] == 0:
                que.append((i, j))

    L = deque()
    while que:
        now = que.popleft()
        L.append(now)

        while edges[now]:
            to = edges[now].popleft()
            deg[to] -= 1
            if deg[to] == 0:
                que.append(to)

    for _, e in edges.items():
        if e:
            print('-1')
            return

    ans = 0
    while L:
        V = set()
        while L:
            player, enemy = L[0]
            if player in V or enemy in V:
                break
            V.add(player)
            V.add(enemy)
            L.popleft()
        ans += 1

    print(ans)

sol()

### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')


def sol():
    N = int(input())
    A = [deque()] + [deque(map(int, input().split())) for _ in range(N)]

    days = [0] * (N + 1)
    now = [0] * (N + 1)

    que = deque([i + 1 for i in range(N)])

    while que:
        i = que.popleft()
        if not A[i]:
            continue

        a = A[i].popleft()
        if now[a] == i:
            days[a] = days[i] = max(days[a], days[i]) + 1
            que.append(i)
            que.append(a)
            now[a] = now[i] = 0
        else:
            now[i] = a

    for i in range(1, N + 1):
        if A[i]:
            print(-1)
            return
    print(max(days))


sol()
### BUGGY CODE ###

n = int(input())
al = [int(input()) for _ in range(n)]

for i in range(n):
    tmp = al[:i] + al[i+1:]
    print(max(tmp))

### FIXED CODE ###

n = int(input())
al = list(int(input()) for _ in range(n))
al_s = sorted(list(set(al)), reverse=True)

if al.count(al_s[0]) == 1:
    for a in al:
        if a != al_s[0]:
            print(al_s[0])
        else:
            print(al_s[1])
else:
    for i in range(n):
        print(al_s[0])
### BUGGY CODE ###

from collections import defaultdict
from itertools import permutations

N,M,R=map(int,input().split())
r=[int(x) for x in input().split()]

INF=10**20
d=[[INF for x in range(N)] for y in range(N)]

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

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

ans=INF
warshall_floyd(N)
for root in permutations(r):
  cnt=0
  for i in range(len(root)-1):
    cnt+=d[root[i]-1][root[i+1]-1]
    if cnt>ans:
      break
  ans=min(ans,cnt)
print(ans)


### FIXED CODE ###

from itertools import permutations

N,M,R=map(int,input().split())
r=[int(x) for x in input().split()]

INF=float('inf')
d=[[INF for x in range(N)] for y in range(N)]

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

for i in range(N):
  for j in range(N):
    for k in range(N):
      if d[j][i]+d[i][k] < d[j][k]:
        d[j][k]=d[j][i]+d[i][k]

ans=INF
for root in permutations(r):
  cnt=0
  for i in range(R-1):
    cnt+=d[root[i]-1][root[i+1]-1]
    if cnt>ans:
      break
  ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(n):
  ans += i
print(ans)

### FIXED CODE ###

n = int(input())
ans = n*(n-1)//2
print(ans)
### BUGGY CODE ###

from itertools import combinations
x,y=map(int,input().split())
z=[4]*x
l=[2]*x
for i in z:
	l.append(i)
c=combinations(l,x)
v=0
for i in c:
	if sum(i)==y:
		print("Yes")
		v=1
		break
if v==0:
	print("No")

### FIXED CODE ###

from itertools import combinations
x,y=map(int,input().split())
if y%2!=0:
	print("No")
else:
	if 2*x==y or 4*x==y:
		print("Yes")
	else:
		v=0
		for i in range(1,x+1):
			if 2*i+4*(x-i)==y or 4*i+2*(x-i)==y:
				print("Yes")
				v=1
				break
		if v==0:
			print("No")
### BUGGY CODE ###

N,M = map(int,input().split())
a=[0]*M
b=[0]*M
c=[] #最初の候補地

for i in range(M):
  a[i],b[i]=map(int,input().split())
  if a[i]==1:
    c.append(b[i])
    
for j in range(M):
  if a[j] in c:
    if b[j]==N:
      print("POSSIBLE")
      break
else:
  print("IMPOSSIBLE")

### FIXED CODE ###

N,M = map(int,input().split())
a=[0]*M
b=[0]*M
c=set() #最初の候補地

for i in range(M):
  a[i],b[i]=map(int,input().split())
  if a[i]==1:
    if b[i] not in c:
      c.add(b[i])
    
for j in range(M):
  if a[j]!=1:
    if a[j] in c:
      if b[j]==N:
        print("POSSIBLE")
        break
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

S = input()
det = 0
count = 0

while True:
  #"BW"の並びがあることを検出する。
  for i in range(len(S)-1):
    if (S[len(S) - i - 1] == "W") and (S[len(S) - i - 2] == "B"):
      det += 1
  if det == 0:
    break
  else:
    det = 0
    for i in range(len(S)-1):
      if (S[len(S) - i - 1] == "W") and (S[len(S) - i - 2]) == "B":
        if i == 0:
          S = S[:len(S) - i - 2] + "WB"
          count += 1
          break
        elif 0 < i < len(S) - 1:
          S = S[:len(S) - i - 2] + "WB" + S[len(S) - i:]
          count += 1
          break
        else:
          S = "WB" + S[len(S) - i:]
          count += 1
          break

print(count)

### FIXED CODE ###

S = input()
white = []
count = 0

for i in range(len(S)):
  if S[i] == "W":
    white.append(i)

for i in range(len(white)):
  count += white[i] - i

print(count)
### BUGGY CODE ###

import numpy as np

h, w = map(int, input().split())
a = [input() for _ in range(h)]

a = np.array([[(ai[j] == "#") for j in range(w)] for ai in a])


ans = 0
for _ in range(h + w):
    if np.all(a):
        break
    a_new = a.copy()

    for i in range(h):
        for j in range(w):
            if (not a_new[i, j]) and (
                (i != 0 and a[i - 1, j])
                or (i != h - 1 and a[i + 1, j])
                or (j != 0 and a[i, j - 1])
                or (j != w - 1 and a[i, j + 1])
            ):
                a_new[i, j] = True
    a = a_new
    ans += 1

print(ans)


### FIXED CODE ###

import numpy as np
from scipy.ndimage.morphology import distance_transform_cdt

h, w = map(int, input().split())
a = [input() for _ in range(h)]

a = np.array([[(ai[j] != "#") for j in range(w)] for ai in a])
d = distance_transform_cdt(a, metric="taxicab").max()
print(d)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from heapq import heapify, heappush, heappop


def solve(N: int, A: "List[int]", B: "List[int]"):

    lh = []
    for i, b in enumerate(B):
        heappush(lh, [-b, i])

    count = 0
    while lh:
        b, i = heappop(lh)
        a, b = A[i], B[i]
        c = B[i-1]+B[(i+1) % N]
        if b > a and b >= c:
            d, m = divmod(b-a, c)
            if d == 0:
                break
            count += d
            B[i] = a+m
            if m != 0:
                heappush(lh, [-B[i], i])

    if A != B:
        count = -1

    print(count)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# import heapq


def solve(N: int, A: "List[int]", B: "List[int]"):

    count = 0
    flag = True
    while flag:
        flag = False
        for i in range(N):
            a, b, c = B[i-1], B[i], B[(i+1) % N]
            if b > A[i] and b > a+c:
                d, m = divmod(b-A[i], a+c)
                if m == 0:
                    B[i] = A[i]
                    count += d
                else:
                    d, m = divmod(b, a+c)
                    count += d
                    B[i] = m
                flag = True
    # print(*A)
    # print(*B)
    if A != B:
        count = -1

    print(count)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)


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

n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(len(l)-2):
    for j in range(i+1, len(l)-1):
        a1 = l[i] + l[j]
        for k in range(j+1, len(l)):
            if l[k] < a1:
                ans += 1
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(len(l)-2):
    for j in range(i+1, len(l)-1):
        a1 = l[i] + l[j]
        index = bisect.bisect_left(l, a1)
        if index:
            ans += index - j - 1
print(ans)