Harryxun/stf_run huggingface dataset:
from sys import stdin


class DFS():
    def __init__(self,N,S):
        self.N = N
        self.S = S
        self.seen = [False] * self.N
        self.cnt = [0] * self.N

    def dfs(self, i):
        if i == self.N-1:
            return 1
        elif i > self.N-1:
            return 0
        elif self.seen[i]:
            return self.cnt[i]
        else:
            cnt = 0
            for s in self.S:
                cnt += self.dfs(i+s)
            else:
                self.cnt[i] = cnt % 998244353
                self.seen[i] = True
            return self.cnt[i]


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        L_R_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = 0
    S = []
    for L, R in L_R_arr:
        S.extend([i for i in range(L, R+1)])

    dfs = DFS(N, S)
    dfs.dfs(0)
    ans = dfs.cnt[0] % 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin
import sys
sys.setrecursionlimit(10**7)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        L_R_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dp = [0] * N
    sdp = [0] * (N+1)
    dp[0] = 1
    for i in range(N):
        for L, R in L_R_arr:
            right = max(0, i-L+1)
            left  = max(0, i-R)
            dp[i] += sdp[right] - sdp[left]
        else:
            sdp[i+1] = (sdp[i] + dp[i]) % 998244353
    ans = dp[-1] % 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()
import sys

_, s = sys.stdin.read().split('\n')
red_hat_counter = 0
blue_hat_counter = 0


# Get a counter of Red
for s_char in s:
  if s_char == "R":
    red_hat_counter += 1
  else:
    blue_hat_counter += 1

# Compare between a criteria value and a counter of Red
if blue_hat_counter < red_hat_counter:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys
input_list = sys.stdin.readlines() 
N, s = map(str.strip, input_list)
red_hat_counter = 0
for s_str in s:
  if s_str == "R":
    red_hat_counter += 1
if red_hat_counter > (int(N)/2):
  print "Yes"
else:
  print "No"
A,B,K =[int(_) for _ in input().split()]

def fgcd(a,b):
    while b:
        a,b = b,a%b
    return a

igcd = fgcd(A,B)
if igcd == 1:
    print(1)
else:
    aP = (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97)
    aD =[igcd,1]
    for eP in aP:
        if igcd % eP == 0:
            aD.append(eP)
            i = 1
            while igcd % (eP**i) == 0 :
                aD.append(igcd // (eP ** i))
                i += 1
    aD = sorted(list(set(aD)),reverse=True)
    print(aD[K-1])


### FIXED CODE ###

A,B,K =[int(_) for _ in input().split()]

iC = 0
for i in range(100,0,-1):
    if A % i == 0 and B % i ==0:
        iC += 1
        if K == iC:
            print(i)
            exit()
a,b,c,d=map(int,input().split())
if a+b>c+d:
  print('Left')
elif a+b=c+d:
  print('Balanced')
else:
  print('Right')

### FIXED CODE ###

a,b,c,d=map(int,input().split())
if a+b>c+d:
  print('Left')
elif a+b==c+d:
  print('Balanced')
else:
  print('Right')
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

def find(LI,i,j,p):
    data=[(0,1),(0,-1),(1,0),(-1,0)]
    if not (0<=i<h and 0<=j<w):
        LI[i][j]=-1
        return LI[i][j]

    if s[i][j]=="#":
        LI[i][j] = -1
        return LI[i][j]
        
    if LI[i][j]!=-2:
        return LI[i][j]
    else:
        LI[i][j]= find(LI, i+data[p][0], j+data[p][1], p)+1
        return LI[i][j]
    

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
R=[[-2]*w for i in range(h)]
L=[[-2]*w for i in range(h)]
F=[[-2]*w for i in range(h)]
B=[[-2]*w for i in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        find(R,i,j,0)
        find(L,i,j,1)
        find(F,i,j,2)
        find(B,i,j,3)
        if s[i][j]!="#":
            ans = max(ans, sum((R[i][j], L[i][j], F[i][j], B[i][j]))+1)
print(ans)



### FIXED CODE ###

h,w=map(int,input().split())
data=[list(input()) for i in range(h)]
yoko=[[0]*w for i in range(h)]
for i in range(h):
	j=0
	while j <w:
		if data[i][j]=='#':
			j+=1
		else:
			start=j
			while j<w-1:
				j+=1
				if data[i][j]=='#':
					for k in range(start,j):
						yoko[i][k]=j-start-1
					j+=1
					break
			else:
				j+=1
				for k in range(start,j):
					yoko[i][k]=j-start-1
				j+=1
# for i in range(h):
# 	print(yoko[i])

for j in range(w):
	i=0
	while i <h:
		if data[i][j]=='#':
			i+=1
		else:
			start=i
			while i<h-1:
				i+=1
				if data[i][j]=='#':
					for k in range(start,i):
						yoko[k][j]+=i-start-1
					i+=1
					break
			else:
				i+=1
				for k in range(start,i):
					yoko[k][j]+=i-start-1
				i+=1

# print(yoko)
for i in range(h):
	# print(yoko[i])
	yoko[i]=max(yoko[i])
print(max(yoko)+1)
n, m = map(int, input().split())
h = list(map(int, input().split()))
l = []
for i range (m):
    a, b = map(int, input().split())
    l.append([a, b])

ll = [0]*n

for j in l:
    if h[j[0] - 1] > h[j[1] - 1]:
        ll[j[1] - 1] += 1
    elif h[j[0] - 1] > h[j[1] - 1]:
        ll[j[1] - 1] += 1
        ll[j[0] - 1] += 1
    else:
        ll[j[0] - 1] += 1

ans = 0

for k in ll:
    if k == 0:
        ans += 1
    else:
        ans += 0
    
print(ans)

### FIXED CODE ###

import copy

n, m = map(int, input().split())
h = list(map(int, input().split()))
l = []
for i in range(m):
    a, b = map(int, input().split())
    l.append([a, b])

ll = [0]*n

for j in l:
    if h[j[0] - 1] > h[j[1] - 1]:
        ll[j[1] - 1] += 1
    elif h[j[0] - 1] == h[j[1] - 1]:
        ll[j[1] - 1] += 1
        ll[j[0] - 1] += 1
    else:
        ll[j[0] - 1] += 1

ans = 0

for k in ll:
    if k == 0:
        ans += 1
    else:
        ans += 0
    
print(ans)
def main():
    N = int(input())
    TA = list(map(int, input().split()))
    T, A = TA[0], TA[1]
    H = list(map(int, input().split()))
    arr = []
    ondo = 0
    for i in range(N):
        ondo = int(T - H[i] * 0.006)
        arr.append([ondo, i+1])
    for j in range(1, N):
        res1 = A - arr[j-1][0]
        res2 = A - arr[j][0]
        if res1 < res2:
            ans = arr[j-i][1]
        else:
            ans = arr[j][1]
    print(ans)
main(

### FIXED CODE ###

def main():
    N = int(input())
    TA = list(map(int, input().split()))
    T, A = TA[0], TA[1]
    H = list(map(int, input().split()))

    temp1 = abs(A - (T - H[0] * 0.006))
    pos = 0

    for i in range(1, N):
        temp2 = abs(A - (T - H[i] * 0.006))
        if temp1 > temp2:
            temp1 = temp2
            pos = i
    print(pos+1)

if __name__  == '__main__':
    main()
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab.sort()
ans = 0
cnt = 0
i = 0
while cnt < m:
    ans += ab[i][0]*ab[i][1]
    cnt += ab[i][1]
    i += 1
print(ans - (cnt - m)*ab[i][0])

### FIXED CODE ###

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab.sort()
ans = 0
cnt = 0
i = 0
while cnt < m:
    ans += ab[i][0]*ab[i][1]
    cnt += ab[i][1]
    i += 1
print(ans - (cnt - m)*ab[i-1][0])
def f(n):
    s=str(n)
    return sum([int(s[i]) for i in range(len(s))])

sunuke=[]
for i in range(100):
    for j in range(2,11):
        sunuke.append(j*(10**i)-1)
L=len(sunuke)
tmp1,tmp2=sunuke[L-1],f(sunuke[L-1])
ans=[sunuke[L-1]]
for i in range(len(sunuke)-2,-1,-1):
    x=sunuke[i]
    if x*tmp2<=tmp1*f(x):
        ans.append(x)
        tmp1,tmp2=x,f(x)

ans.sort()

    

for i in range(int(input())):
    print(ans[i])


### FIXED CODE ###

s=input()
ans=0
for i in range(4):
    if s[i]=="+": ans+=1
    else: ans-=1

print(ans)
a,b = map(int, input().split())
n = 1
if b == 1:
    print(0)
else:
    while a*n-(n-1) < b:
        n += 1
    print(n)


### FIXED CODE ###

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

total = 0
for i in range(n):
    total += b[a[i] - 1]
    if i < n-1:
        if a[i] + 1 == a[i+1]:
            total += c[a[i]-1]
print(total)
A=int(input())
B=int(input())
C=int(input())
X=int(input())
counti = 0

for a in range(A)+1:
  for b in range(B)+1:
    for c in range(C)+1:
      if 500*a + 100*b + 50*c == X:
        counti += 1

print(counti)

### FIXED CODE ###

A=int(input())
B=int(input())
C=int(input())
X=int(input())
counti = 0

for a in range(A+1):
  for b in range(B+1):
    for c in range(C+1):
      if 500*a + 100*b + 50*c == X:
        counti += 1

print(counti)
n,m = map(int, input().split())

ac = [False]*n
c_ac = 0
c_wa = 0

for _ in range(m):
    pi,si = input().split()
    pi = int(pi)
    
    if ac[pi] == False:
        if si == 'WA':
            c_wa += 1
        elif si == 'AC':
            c_ac += 1
            ac[pi] = True

print(c_ac, c_wa)

### FIXED CODE ###

n,m = map(int, input().split())

ac = [False]*n
c_ac = 0
c_wa = 0
wa = [0]*n
for _ in range(m):
    pi,si = input().split()
    pi = int(pi) - 1
    
    if ac[pi] == False:
        if si == 'WA':
            wa[pi] += 1
        elif si == 'AC':
            c_ac += 1
            c_wa += wa[pi]
            ac[pi] = True

print(c_ac, c_wa)
import bisect
def f(x,a):
  global N,M
  if M==0:
    return False
  b = bisect.bisect_left(a,x)
  return True if x==a[mi
  n(b,N)] else False
MOD = 10**9+7
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)

### FIXED CODE ###

import bisect
def f(x,a):
  global M
  b = bisect.bisect_left(a,x)
  if x==a[min(b,M)]:
    return True
  else:
    return False
MOD = 10**9+7
N,M = map(int,input().split())
a = [-1]+[int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)
[K, X] = [int(x) for x in input().split()]
if K * 500 >= X:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N = int(input())
S = str(input())
print(S.count("ABC"))
def abs(k):
  if k >= 0:
    return k
  else:
    return -k

a, b, c ,n = list(map(int,input().split()))
i for i in range(n):
  a = b + c
  b = c + a 
  c = a + b
res = a - b
if abs(res) > 10 ** 18:
  print('Unfair')
else:
  print(res)

### FIXED CODE ###

A, B, C, K = map(int, input().split())
print(A - B if K % 2 == 0 else B - A)
N = int(input())
A = list(map(int, input().split()))

import collections
dic=dict(collections.Counter(A))
li=list(dic.values())

ans='No'

if len(li)==3:
    if N%3 == 0:
        
        if li[0]== N/3 and li[1]==N/3:
            se=li[5]
            ans='Yes'           
elif len(li)==2:
    if N%3 == 0:
        if li[0]== 2*N/3 or li[1]==2*N/3:
            ans='Yes'
elif len(li)==1:
        if list(dic.keys())[0]==0:
            ans='Yes'

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter

def main():
    N = int(input())
    a = list(map(int, input().split()))
    l = Counter(a)
    if len(l)==1 and 0 in l:
        print('Yes')
        exit()
    if N%3==0 and len(l)==2 and 0 in l and l[0] == N//3:
        print('Yes')
        exit()
    if N%3==0 and len(l)==3:
        x,y,z = l.keys()
        if l[x] == l[y] == N//3 and x^y^z == 0:
            print('Yes')
            exit()
    print('No')

    

if __name__ == '__main__':
    main()
N,M=[int(x) for x in input().split()]
I=[[] for n in range(N)]
G=[n for n in range(N)]
W=[1 for n in range(N)]
E=[]

result=[]
ans = int(N * (N-1) / 2)

def union(i,g):
    if(G[i]!=g):
        G[i]=g
        for n in I[i]:
            union(n,g)

for m in range(M):
    A,B=[int(x) for x in input().split()]
    E.append((A-1,B-1))

for m in range(M):
    result.append(ans)
#    print(E)
    if(ans>0):
        A,B=E.pop()
        Ga,Gb=G[A],G[B]
        Wa,Wb=W[Ga],W[Gb]
#        print("%i=%i-(%i*%i)" % (ans-(Wa*Wb),ans,Wa,Wb))
        ans=ans-(Wa*Wb)
        I[A].append(B)
        I[B].append(A)
        if (Wb>Wa):
            union(Ga,Gb)
            W[Gb]=Wa+Wb
        else:
            union(Gb,Ga)
            W[Ga]=Wa+Wb
#    print(I)
#    print(G)
#    print(W)
#    print("----")

for r in reversed(result):
    print(r)


### FIXED CODE ###

N,M=[int(x) for x in input().split()]
G=[-1] * N
W=[0] * N
E=[]

result=[]
ans = int(N * (N-1) / 2)

def union(i,j):
    gi=find(i)
    gj=find(j)

    if(gi!=gj):
        if W[gi] > W[gj]:
            G[gi]+=G[gj]
            G[gj]=gi
        else:
            G[gj]+=G[gi]
            G[gi]=gj
            if W[gi]==W[gj]:
                W[gj]+=1

def find(i):
    if G[i]<0:
        return i;
    else:
        G[i]=find(G[i])
        return G[i]

for m in range(M):
    A,B=[int(x) for x in input().split()]
    E.append((A-1,B-1))

for m in range(M):
    result.append(ans)
    if(ans>0):
        A,B=E.pop()
        ga,gb=find(A),find(B)
        if (ga!=gb):
            ans=ans-(G[ga]*G[gb])
            union(A,B)

for r in reversed(result):
    print(r)
from collections import deque
from sys import stdin

def bfs():
    readline=stdin.readline
    h,w=map(int,readline().split())
    sy,sx=map(int,readline().split())
    gy,gx=map(int,readline().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(readline()) for _ in range(h)]
    dict={".":10000000,"#":-1}
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[(i,j) for i in range(-2,3) for j in range(-2,3)]
    while que:
        y,x=que.popleft()
        s1=s[y][x]
        nexty,nextx=y+i,x+j
        for (i,j) in temp:
            if 0<=nexty<h and 0<=nextx<w and s[nexty][nextx]>=0:
                dist=s[nexty][nextx]
                if i*i+j*j<=1 and dist>s1:
                    s[nexty][nextx]=s1
                    que.append([nexty,nextx])
                elif dist>s1+1:
                    s[nexty][nextx]=s1+1
                    que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])
bfs()


### FIXED CODE ###

from collections import deque
from sys import stdin

def bfs():
    readline=stdin.readline
    h,w=map(int,readline().split())
    sy,sx=map(int,readline().split())
    gy,gx=map(int,readline().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(readline()) for _ in range(h)]
    dict={".":10000000,"#":-1}
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[i for i in range(-2,3)]
    while que:
        y,x=que.popleft()
        s1=s[y][x]
        for i in temp:
            nexty=y+i
            if 0<=nexty<h:
                s2=s[nexty]
                for j in temp:
                    nextx=x+j
                    if 0<=nextx<w and s2[nextx]>=0:
                        dist=s2[nextx]
                        if i*i+j*j<=1 and dist>s1:
                            s[nexty][nextx]=s1
                            que.appendleft([nexty,nextx])
                        elif dist>s1+1:
                            s[nexty][nextx]=s1+1
                            que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])
bfs()
import itertools
import math
MOD = 1000000007
def P(n, r):
  return math.factorial(n)//math.factorial(n-r)
def C(n, r):
  return P(n, r)//math.factorial(r)% MOD
def X(n, r):
  try:
    return C(n-1,n-r) 
  except:
    return 0
N,K = map(int,input().split())

for i in range(1,K+1):
  if (1==i and K==N):
    print (1)
  else:
    #print (X(K,i)*((X(N-K,i+1)+2*X(N-K,i)+X(N-K,i-1)))% MOD)
    print ((C(N-K+1,i)*C(K-1,i-1))% MOD)


### FIXED CODE ###

import itertools
import math
MOD = 1000000007
def P(n, r):
  return math.factorial(n)//math.factorial(n-r)
def C(n, r):
  return P(n, r)//math.factorial(r)% MOD
def X(n, r):
  try:
    return C(n-1,n-r) 
  except:
    return 0
N,K = map(int,input().split())

for i in range(1,K+1):
  if (1==i and K==N):
    print (1)
  else:
    print (X(K,i)*((X(N-K,i+1)+2*X(N-K,i)+X(N-K,i-1)))% MOD)
import fractions
import math

tmp = list(map(int,(input().split())))
a = tmp[0]
b = tmp[1]

#limit = fractions.gcd(a, b)
limit = min(fractions.gcd(a, b), int(math.sqrt(a)), int(math.sqrt(b)))
cnt = 0
for i in range(2, limit+1):
  flag = False
  while (a % i == 0) and (b % i == 0):
    a = a // i
    b = b // i
    flag = True
  if flag:
    cnt += 1

last = min(a, b)
flag = False
if (a % last == 0) and (b % last == 0) last > 1:
  cnt += 1

   
print (cnt+1)

### FIXED CODE ###

import fractions
import math
from collections import deque

def prime(x):
  px = []
  limit = int(math.sqrt(x))
  for i in range(2, limit+1):
    flag = False
    while x % i == 0:
      flag = True
      x = x // i
    if flag:
      px.append(i)
  if x != 1:
    px.append(x)
  return px

tmp = list(map(int,(input().split())))
a = tmp[0]
b = tmp[1]

pa = prime(a)
pb = prime(b)

cnt = 1
j = 0

for i in range(len(pa)):
  while j < len(pb) and pb[j] < pa[i]:
    j += 1
  if j == len(pb):
    break
  elif pb[j] == pa[i]:
    cnt += 1
  
print (cnt)
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

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

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, C = na()
ans = [0] * ((10 ** 5) * 2 + 10)
for i in range(N):
    s, t, c = na()
    ans[s] += 1
    ans[t+1] -= 1

for i in range(len(ans)-1):
    ans[i+1] += ans[i]
print(min(max(ans)), C)

 






### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

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

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, C = na()
ans = [0] * ((10 ** 5) * 2 + 10)
for i in range(N):
    s, t, c = na()
    ans[s] += 1
    ans[t+1] -= 1

for i in range(len(ans)-1):
    ans[i+1] += ans[i]
print(min(max(ans), C))
arr=list(map(int,input().split())
n=arr[0]
m=arr[1]
if n==m:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

arr=list(map(int,input().split()))
n=arr[0]
m=arr[1]
if n==m:
  print("Yes")
else:
  print("No")
from collections import deque
import copy


def bfs(start, s):
    h = len(s)
    w = len(s[0])
    distance = 0
    maze = [[-1] * w for _ in range(h)]
    maze[start[0]][start[1]] = 0
    s[start[0]][start[1]] = "#"
    drcs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    q = deque()
    q.append(start)
    while(q):
        cr, cc = q.popleft()
        for dr, dc in drcs:
            nr, nc = cr + dr, cc+ dc
            if nr < 0 or nc < 0 or nr >= h or nc >= w:
                continue
            if s[nr][nc] == ".":
                q.append([nr, nc])
                s[nr][nc] == "#"
                maze[nr][nc] = maze[cr][cc] + 1
                if maze[nr][nc] > distance:
                    distance = maze[nr][nc]
                    goal = [nr][nc]
    return goal, distance
    


def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    for r in range(h):
        if "." in s[r]:
            start = [r, s[r].index(".")]
    goal, distance = bfs(start, copy.deepcopy(s))
    _, res = bfs(goal, s)
    print(res)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
import copy


def bfs(start, s):
    h = len(s)
    w = len(s[0])
    distance = 0
    maze = [[-1] * w for _ in range(h)]
    maze[start[0]][start[1]] = 0
    s[start[0]][start[1]] = "#"
    drcs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    q = deque()
    q.append(start)
    while(q):
        cr, cc = q.popleft()
        for dr, dc in drcs:
            nr, nc = cr + dr, cc + dc
            if nr < 0 or nc < 0 or nr >= h or nc >= w:
                continue
            if s[nr][nc] == ".":
                q.append([nr, nc])
                s[nr][nc] = "#"
                maze[nr][nc] = maze[cr][cc] + 1
                if maze[nr][nc] > distance:
                    distance = maze[nr][nc]
                    goal = [nr, nc]
    return goal, distance
    


def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    for r in range(h):
        if "." in s[r]:
            start = [r, s[r].index(".")]
    goal, distance = bfs(start, copy.deepcopy(s))
    _, res = bfs(goal, s)
    print(res)


if __name__ == '__main__':
    main()
import math
n, m = map(int, input().split())
S = input()
T = input()
L = (n*m) // math.gcd(n, m)
c = 0

xs = L//n
xt = L//m
step = xs * xt
for i in range(0, L, step):
    if S[i//xs] != T[i//xt]:
        print(-1)
        exit()
print(L)


### FIXED CODE ###

def gcd(x, y):
    while y > 0:
        x, y = y, x%y
    return x

n, m = map(int, input().split())
S = input()
T = input()
L = (n*m) // gcd(n, m)
c = 0

xs = L//n
xt = L//m
step = xs * xt

for i in range(0, L, step):
    if S[i//xs] != T[i//xt]:
        print(-1)
        exit()
print(L)
n=list(input())
n_list=[int(i) for i in n]
if n_list[0]!=1 and set(n_list)!=[9]:
  ans=9*(len(n_list)-1)+n_list[0]-1
  print(ans)
elif n_list[0]!=1 and set(n_list)==[9]:
  print(9*len(n_list))
elif n_list[0]+n_list[1]<=9:
  ans=(len(n_list)-1)*9
else:
  ans=n_list[0]+n_list[1]-1+9*(len(n_list)-2)
  
  

### FIXED CODE ###

N = input()
ans = 0

if N[1:] == "9" * (len(N) - 1):
    ans = int(N[0]) + (9 * (len(N) - 1))
else:
    ans = int(N[0]) + 9 * (len(N) - 1) - 1

print(ans)
n,m=map(int,input().split())
if n==m:
  print("Yes")
else:
  print("No
        ")

### FIXED CODE ###

n,m=map(int,input().split())
if n==m:
  print("Yes")
else:
  print("No")
from collections import Counter

while True:
    m, n = (int(s) for s in input().split())
    if not m:
        break

    objs = [int(input(), 2) for i in range(n)]
    f = [[0 for i in range(1 << m)] for i in range(1 << m)]

    for mask in reversed(range(1<<m)):
        s = Counter(obj & mask for obj in objs)
        for mask0 in range(mask + 1):
            if s[mask0] > 1:
                f[mask][mask0] = n + 1
                for b in [1<<k for k in range(m)]:
                    if not (b & mask):
                        f[mask][mask0] = min(f[mask][mask0],
                                             max(f[mask + b][mask0],
                                                 f[mask + b][mask0 + b]) + 1
                                             )
    print(f[0][0])

### FIXED CODE ###

from collections import Counter

while True:
    m, n = (int(s) for s in input().split())
    if not m:
        break

    objects = [int(input(), 2) for i in range(n)]
    dp = [bytearray(1 << m) for i in range(1 << m)]
    bits = [1 << i for i in range(m)]

    for asked in reversed(range((1 << m) - 1)):
        for masked, count in Counter(obj & asked for obj in objects).items():
            if count > 1:
                dp[asked][masked] = min(max(dp[asked + b][masked],
                                            dp[asked + b][masked + b])
                                        for b in bits if not b & asked) + 1
    print(dp[0][0])