Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.
The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is #, and a "road" square if S_{ij} is ..
From a road square, you can move to a horizontally or vertically adjacent road square.
You cannot move out of the maze, move to a wall square, or move diagonally.
Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.
Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.
In this situation, find the maximum possible number of moves Aoki has to make.

-----Constraints-----
 - 1 \leq H,W \leq 20
 - S_{ij} is . or #.
 - S contains at least two occurrences of ..
 - Any road square can be reached from any road square in zero or more moves.

-----Input-----
Input is given from Standard Input in the following format:
H W
S_{11}...S_{1W}
:
S_{H1}...S_{HW}

-----Output-----
Print the maximum possible number of moves Aoki has to make.

-----Sample Input-----
3 3
...
...
...

-----Sample Output-----
4

If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.

Difficulty: interview

Starter code:

Solutions:
from collections import deque
from copy import deepcopy

h,w = map(int,input().split())
s = [list(input()) for i in range(h)]
t = ((0,1),(1,0),(-1,0),(0,-1))
m = 0
for sy in range(h):
    for sx in range(w):
        if s[sy][sx] == "#":
            continue
        ss = deepcopy(s)
        ss[sy][sx] = "#"
        q = deque([(0,sy,sx)])
        max_cost = 0
        my,mx = 0,0
        while(q):
            cost,y,x = q.popleft()
            max_cost = max(max_cost,cost)
            cost += 1
            for i,j in t:
                ny = y+i
                nx = x+j
                if 0 <= ny < h and 0 <= nx < w:
                    if ss[ny][nx] == ".":
                        q.append((cost,ny,nx))
                        ss[ny][nx] = "#"
        m = max(m,max_cost)
print(m)

from collections import deque


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


def LSH(h):
    return [input() for _ in range(h)]


H, W = LI()
Fi = LSH(H)
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for sh in range(H):  # スタート位置全部試します
    for sw in range(W):
        if Fi[sh][sw] == "#":
            continue
        d = deque()
        d.append([sh, sw])
        looked = [[0 for i in range(W)]for j in range(H)]
        looked[sh][sw] = 1
        while d:
            h, w = d.popleft()
            for i in move:
                a = h+i[0]
                b = w+i[1]
                if not(0 <= a < H) or not(0 <= b < W) or Fi[a][b] == "#" or looked[a][b] != 0:
                    continue
                d.append([a, b])
                looked[a][b] = looked[h][w]+1
            if len(d) == 0:
                ans = max(ans, looked[h][w]-1)
print(ans)


import queue
H, W = map(int, input().split())
S = [ list(input()) for _ in range(H)]
ans = 0
for sx in range(H):
    for sy in range(W):
        if S[sx][sy] == '#': continue
        
        D = [[float('inf') for _ in range(W)] for _ in range(H)]
        D[sx][sy] = 0
        q = queue.Queue()
        q.put((sx, sy))
        
        vs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        while not q.empty():
            x, y = q.get()
            for dx, dy in vs:
                nx = x + dx
                ny = y + dy
                if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != '#' and D[nx][ny] == float('inf'):
                    q.put((nx, ny))
                    D[nx][ny] = D[x][y] + 1

        for gx in range(H):
            for gy in range(W):
                if S[gx][gy] == '#': continue
                ans = max(ans, D[gx][gy])

print(ans)

import queue
import copy
q = queue.Queue()
h, w = list(map(int, input().split()))
a = [list('#'+input()+'#') for _ in range(h)]
a = [['#']*(w+2)]+a+[['#']*(w+2)]
a1 = copy.deepcopy(a)
ans = []
        
for i in range(1, h+1):
    for j in range(1, w+1):
        a = copy.deepcopy(a1)
        if a[i][j] == '#':
            continue        
        q.put([i, j, 0])
        while not q.empty():
            now = q.get()
            
            if a[now[0]][now[1]] == '.':
                ans.append(now[2])
                a[now[0]][now[1]] = '#'
            else:
                continue
                
            if a[now[0]+1][now[1]] != '#':
                q.put([now[0]+1, now[1], now[2]+1])
            if a[now[0]-1][now[1]] != '#':
                q.put([now[0]-1, now[1], now[2]+1])
            if a[now[0]][now[1]+1] != '#':
                q.put([now[0], now[1]+1, now[2]+1])
            if a[now[0]][now[1]-1] != '#':
                q.put([now[0], now[1]-1, now[2]+1])
        a1[i][j] == '#'
print((max(ans)))


#!/usr/bin/env python3
from collections import deque

h, w = list(map(int, input().split()))
maze = [input() for _ in range(h)]
ans = 0


def bfs(sx, sy):
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    d = [[-1] * w for _ in range(h)]
    q = deque([])

    q.append((sx, sy))
    d[sx][sy] = 0
    ans = 0

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][
                    ny] == -1:
                q.append((nx, ny))
                d[nx][ny] = d[x][y] + 1
                ans = max(ans, d[nx][ny])
    return ans


for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs(i, j))
print(ans)


H,W=map(int,input().split())
S=[list(input())for _ in range(H)]

from collections import deque
def bfs(h,w,sy,sx,S):
    maze=[[10**9]*(W)for _ in range(H)]
    maze[sy-1][sx-1]=0
    que=deque([[sy-1,sx-1]])
    count=0
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<h and 0<=nextx<w:
                dist1=S[nexty][nextx]
                dist2=maze[nexty][nextx]
            else:
                continue
            if dist1!='#':
                if dist2>maze[y][x]+1:
                    maze[nexty][nextx]=maze[y][x]+1
                    count=max(count,maze[nexty][nextx])
                    que.append([nexty,nextx])
    return count

ans=0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx]=='.':
            now=bfs(H,W,sy+1,sx+1,S)
            ans=max(ans,now)

print(ans)

from collections import deque
import sys
import copy

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


### BFS ###

nextH = [0, 1, 0, -1]
nextW = [1, 0, -1, 0]


def bfs(u, S):

    S[u[0]][u[1]] = 0  # state を変更

    q = deque()
    q.append(u)
    m = 0
    while q:
        u = q.popleft()
        for h, w in zip(nextH, nextW):
            h += u[0]
            w += u[1]
            if not (0 <= h < len(S) and 0 <= w < len(S[0])):
                continue

            if S[h][w] == '.':  # state を確認
                S[h][w] = S[u[0]][u[1]] + 1  # state を変更
                m = max(m, S[h][w])
                q.append((h, w))
    
    return m


def main():

    H, W = list(map(int, sys.stdin.readline().rstrip().split()))
    S = []
    for _ in range(H):
        S.append([x for x in sys.stdin.readline().rstrip()])

    # print(S)

    m = 0
    for h in range(H):
        for w in range(W):
            D = copy.deepcopy(S)
            if S[h][w] == '.':
                m = max(m, bfs((h, w), D))

    print(m)


main()


from collections import deque

def getdistance(row,col,sw,h,w):
    maze = deque([[row,col,0]])
    marker = [[0]*w for _ in range(h)]
    marker[row][col] = 1
    while len(maze)!=0:
        r, c, d = maze.popleft()
        if r!=0:
            if sw[r-1][c]!="#" and marker[r-1][c] != 1:
                marker[r-1][c] = 1
                maze.append([r-1,c,d+1])
        if r!=h-1:
            if sw[r+1][c]!="#" and marker[r+1][c] != 1:
                marker[r+1][c] = 1
                maze.append([r+1,c,d+1])
        if c!=w-1:
            if sw[r][c+1]!="#" and marker[r][c+1] != 1:
                marker[r][c+1] = 1
                maze.append([r,c+1,d+1])
        if c!=0:
            if sw[r][c-1]!="#" and marker[r][c-1] != 1:
                marker[r][c-1] = 1
                maze.append([r,c-1,d+1])
    return d
h, w = map(int, input().split())
sw = [input() for _ in range(h)]
ans = 0
for row in range(h):
    for col in range(w):
        if sw[row][col]=="#":
            continue
        ans = max(ans,getdistance(row,col,sw,h,w))
print(ans)

from collections import deque

H,W=list(map(int,input().split()))
S=[[c=='#' for c in input()] for _ in range(H)]

def bfs(i,j):
    if S[i][j]:
        return 0
    que=deque()
    que.append((i,j))
    vis=[row[:] for row in S]
    vis[i][j]=1
    ans=-1
    while que:
        ans+=1
        for _ in range(len(que)):
            i,j=que.popleft()
            for ni,nj in nbs(i,j):
                if not vis[ni][nj]:
                    que.append((ni,nj))
                    vis[ni][nj]=1
    return ans

def nbs(i,j):
    for ni,nj in (i-1,j),(i,j+1),(i+1,j),(i,j-1):
        if 0<=ni<H and 0<=nj<W:
            yield ni,nj

ans=0
for i in range(H):
    for j in range(W):
        ans=max(ans,bfs(i,j))

print(ans)


import sys
from collections import deque

H,W=list(map(int,input().split()))
S=list(sys.stdin)

ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]=='#':
            continue
        dist=[[-1]*W for _ in range(H)]
        dist[i][j]=0
        que=deque()
        que.append((i,j))
        while que:
            i,j=que.popleft()
            ans=max(ans,dist[i][j])
            for ni,nj in (i-1,j),(i,j+1),(i+1,j),(i,j-1):
                if not (0<=ni<H and 0<=nj<W):
                    continue
                if S[ni][nj]=='#' or dist[ni][nj]!=-1:
                    continue
                dist[ni][nj]=dist[i][j]+1
                que.append((ni,nj))

print(ans)


#!/usr/bin/env python3
def main():
    from collections import deque
    import numpy as np

    H, W = list(map(int, input().split()))
    S = [list(input()) for _ in range(H)]

    move = ((0, 1), (0, -1), (1, 0), (-1, 0))
    seen = [[False] * W for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if S[sh][sw] == '#' or seen[sh][sw]:
                continue
            seen[sh][sw] = True
            queue = deque([(sh, sw)])
            # distance = np.zeros((H, W), dtype=np.int16)
            distance = np.full((H, W), -1, dtype=np.int16)
            distance[sh, sw] = 0
            while queue:
                h, w = queue.popleft()
                for dh, dw in move:
                    nh = h + dh
                    nw = w + dw
                    if (1
                            and 0 <= nh < H
                            and 0 <= nw < W
                            and S[nh][nw] == '.'
                            and distance[nh][nw] == -1):
                        distance[nh][nw] = distance[h][w] + 1
                        queue.append((nh, nw))
            ans = max(ans, distance.max())
    print(ans)


def __starting_point():
    main()

__starting_point()

from collections import deque
import copy

H,W=map(int,input().split())
S=[[x for x in input()] for _ in range(H)]
start_list=[]
length=[[-1]*W for _ in range(H)]
ans=0

for i in range(H):
  for j in range(W):
    if S[i][j]=='.':
      start_list.append((i,j))

for start in start_list:
  h,w=start
  d=deque([(h,w)])
  T=copy.deepcopy(S)
  L=copy.deepcopy(length)
  L[h][w]=0
  T[h][w]='#'
  while d:
    h,w=d.popleft()
    
    if h-1>=0 and T[h-1][w]=='.':
      d.append((h-1,w))
      L[h-1][w]=L[h][w]+1
      T[h-1][w]='#'
      ans=max(ans,L[h-1][w])
      
    if h+1<=H-1 and T[h+1][w]=='.':
      d.append((h+1,w))
      L[h+1][w]=L[h][w]+1
      T[h+1][w]='#'
      ans=max(ans,L[h+1][w])
      
    if w-1>=0 and T[h][w-1]=='.':
      d.append((h,w-1))
      L[h][w-1]=L[h][w]+1
      T[h][w-1]='#'
      ans=max(ans,L[h][w-1])
      
    if w+1<=W-1 and T[h][w+1]=='.':
      d.append((h,w+1))
      L[h][w+1]=L[h][w]+1
      T[h][w+1]='#'
      ans=max(ans,L[h][w+1])

print(ans)

from collections import deque
from itertools import product


H, W = list(map(int, input().split()))
S = [input() for _ in range(H)]
route = [[[[400 if S[si][sj]==S[ei][ej]=="." else -1 for ej in range(W)]for ei in range(H)]for sj in range(W)]for si in range(H)]

for i, j in product(list(range(H)), list(range(W))):
    if S[i][j] == ".":
        q = deque([[i, j, i, j]])
        break
while q:
    si, sj, ei, ej = q.pop()
    if (si, sj) == (ei, ej):
        route[si][sj][ei][ej] = 0
    d = route[si][sj][ei][ej]
    for p in [-1, 1]:
        if 0 <= si+p < H and route[si+p][sj][ei][ej] > d+1:
            route[si+p][sj][ei][ej] = d+1
            q.appendleft([si+p, sj, ei, ej])
        if 0 <= sj+p < W and route[si][sj+p][ei][ej] > d+1:
            route[si][sj+p][ei][ej] = d+1
            q.appendleft([si, sj+p, ei, ej])
        if 0 <= ei+p < H and route[si][sj][ei+p][ej] > d+1:
            route[si][sj][ei+p][ej] = d+1
            q.appendleft([si, sj, ei+p, ej])
        if 0 <= ej+p < W and route[si][sj][ei][ej+p] > d+1:
            route[si][sj][ei][ej+p] = d+1
            q.appendleft([si, sj, ei, ej+p])

print((max(route[si][sj][ei][ej] for si, sj, ei, ej in product(list(range(H)), list(range(W)), list(range(H)), list(range(W))))))


# import sys
# sys.setrecursionlimit(10 ** 9)

# H, W = map(int, input().split())
# L = []
# for _ in range(H):
#     s = input()
#     a = []
#     for i in range(len(s)):
#         a.append(s[i])
#     L.append(a)

# dx = [-1, 0, 1, 0]
# dy = [0, -1, 0, 1]


# def dfs(h, w, dp, ans, count):
#     if L[h][w] == '#':
#         return ans
#     elif (L[h][w] == '.' and dp[h][w] == -1):
#         dp[h][w] = 0

#     for i in range(4):
#         if w + dx[i] >= 0 and w + dx[i] < W and h + \
#                 dy[i] >= 0 and h + dy[i] < H:
#             if L[h + dy[i]][w + dx[i]] == '.' and dp[h + dy[i]][w + dx[i]] == -1:
#                 count += 1
#                 ans[h + dy[i]][w + dx[i]
#                                ] = min(ans[h + dy[i]][w + dx[i]], count)
#                 return dfs(h + dy[i], w + dx[i], dp, ans, count)
#             elif L[h + dy[i]][w + dx[i]] == '#':
#                 continue

#     return ans


# max_count = 0
# ans = [[100000000] * W for _ in range(H)]
# for i in range(H):
#     for j in range(W):
#         dp = [[-1] * W for _ in range(H)]
#         count = dfs(i, j, dp, ans, 0)
#         print(count)
#         # max_count = max(max_count, count)

# print(max_count)

# 幅優先探索
from collections import deque
H, W = list(map(int, input().split()))
L = []
for _ in range(H):
    s = input()
    a = []
    for i in range(len(s)):
        a.append(s[i])
    L.append(a)

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]


def bfs(x, y):
    dp = [[10000000] * W for _ in range(H)]
    dp[y][x] = 0
    if L[y][x] == '#':
        return dp
    else:
        d = deque()
        d.append([x, y])
        while len(d) > 0:
            s = d.popleft()
            for i in range(4):
                if (s[1] +
                    dy[i] >= 0 and s[1] +
                    dy[i] < H and s[0] +
                    dx[i] >= 0 and s[0] +
                        dx[i] < W):
                    if L[s[1] +
                         dy[i]][s[0] +
                                dx[i]] == '.' and dp[s[1] +
                                                     dy[i]][s[0] +
                                                            dx[i]] == 10000000:
                        d.append([s[0] + dx[i], s[1] + dy[i]])
                        dp[s[1] + dy[i]][s[0] + dx[i]] = dp[s[1]][s[0]] + 1

        return dp


max_num = 0
for i in range(H):
    for j in range(W):
        dp = bfs(j, i)
        for k in dp:
            for p in k:
                if (p == 10000000):
                    continue
                max_num = max(max_num, p)
print(max_num)


import heapq


def abc151d_maze_master():
    h, w = map(int, input().split())
    s = []
    max_val = 0
    for i in range(h):
        s.append(input())
    for hi in range(h):
        for wi in range(w):
            if s[hi][wi] == '#': continue
            flg = [[-1] * w for _ in range(h)]
            flg[hi][wi] = 0
            q = [(0, hi, wi)]
            heapq.heapify(q)
            while len(q) > 0:
                d, hj, wj = heapq.heappop(q)
                for dh, dw in zip([0, 0, 1, -1], [1, -1, 0, 0]):
                    if 0 <= hj + dh < h and 0 <= wj + dw < w and s[hj + dh][wj + dw] != '#' and \
                            (flg[hj + dh][wj + dw] == -1 or flg[hj + dh][wj + dw] > flg[hj][wj] + 1):
                        heapq.heappush(q, (d + 1, hj + dh, wj + dw))
                        flg[hj + dh][wj + dw] = flg[hj][wj] + 1
                # print(q)
            max_val = max(max_val, max([max(v) for v in flg]))
    print(max_val)


abc151d_maze_master()

from copy import deepcopy
from collections import deque
h, w = map(int, input().split())
s = [["#"]*(w+2)] + [["#"]+list(input())+["#"] for i in range(h)] + [["#"]*(w+2)]
ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        t = deepcopy(s)
        if s[i][j] == "#":
            continue
        a = deque([[i, j, 0]])
        while len(a) > 0:
            x, y, cnt = a.popleft()
            t[x][y] = "#"
            if t[x-1][y] == ".":
                a.append([x-1, y, cnt+1])
                t[x-1][y] = "#"
            if t[x+1][y] == ".":
                a.append([x+1, y, cnt+1])
                t[x+1][y] = "#"
            if t[x][y-1] == ".":
                a.append([x, y-1, cnt+1])
                t[x][y-1] = "#"
            if t[x][y+1] == ".":
                a.append([x, y+1, cnt+1])
                t[x][y+1] = "#"
        ans = max(ans, cnt)
print(ans)

from collections import deque
h,w=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            cnt=[[-1]*w for _ in range(h)]
            cnt[i][j]=0
            queue=deque()
            queue.append([i,j])
            for k in range(100*h*w):
                if len(queue)==0:
                    break
                num=queue.popleft()
                num1=num[0]
                num2=num[1]
                if num1!=0:
                    if s[num1-1][num2]=="." and cnt[num1-1][num2]==-1:
                        cnt[num1-1][num2]=cnt[num1][num2]+1
                        queue.append([num1-1,num2])
                if num2!=0:
                    if s[num1][num2-1]=="." and cnt[num1][num2-1]==-1:
                        cnt[num1][num2-1]=cnt[num1][num2]+1
                        queue.append([num1,num2-1])
                if num1!=h-1:
                    if s[num1+1][num2]=="." and cnt[num1+1][num2]==-1:
                        cnt[num1+1][num2]=cnt[num1][num2]+1
                        queue.append([num1+1,num2])
                if num2!=w-1:
                    if s[num1][num2+1]=="." and cnt[num1][num2+1]==-1:
                        cnt[num1][num2+1]=cnt[num1][num2]+1
                        queue.append([num1,num2+1])
            cnt2=0
            for k in range(h):
                cnt2=max(cnt2,max(cnt[k]))
            ans=max(ans,cnt2)
print(ans)


from copy import deepcopy
from collections import deque
from itertools import product
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid]) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def longest_path(grid, root):
    def restore_route(prev, p):
        A = deque()
        while p:
            A.appendleft(p)
            p = prev[p]
        return list(A)
    
    x, y = root
    prev = {root:None}
    grid[y, x] = '!'
    queue = deque([root])
    while queue:
        x, y = queue.popleft()
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'sg.':
                prev[nx, ny] = x, y
                queue.append((nx, ny))
                grid[ny, nx] = '!'
    return restore_route(prev, (x, y))

h, w = map(int, input().split())
grid = Grid([input() for s in range(h)])
ans = 0
for y, x in product(range(h), range(w)):
    if grid[y, x] == '.':
        path = longest_path(deepcopy(grid), (x, y))
        ans = max(ans, len(path)-1)
print(ans)

h,w = map(int,input().split())
C = [list(input()) for i in range(h)]

queue = []
visited = [] 
visited = [[0 for i in range(w)] for i in range(h)]
ans = 0

for i in range(h):
    for j in range(w):
        if C[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

            while len(queue) > 0:
                now = queue.pop(0)
                for k in range(4):
                    y = now[0]+dy_dx[k][0]
                    x = now[1]+dy_dx[k][1]
                    if 0 <= y < h and 0 <= x < w:
                        if C[y][x] != '#' and visited[y][x] == 0:
                            visited[y][x] = visited[now[0]][now[1]]+1 #移動回数のカウント
                            queue.append([y,x])
                    
        for l in range(h):
            for m in range(w):
                ans = max(ans,visited[l][m])
            
        queue = []
        visited = [[0 for i in range(w)] for i in range(h)]              
        
print(ans-1)

import queue

def bfs(maze,h,w,sy,sx):
    dist=[[-1 for _ in range(w)] for _ in range(h)]
    q=queue.deque([[sy,sx]])
    dist[sy][sx]=0
    while q:
        y,x=q.popleft()
        for dy,dx in d:
            ny,nx=y+dy,x+dx
            if 0<=ny<h and 0<=nx<w and dist[ny][nx]==-1 and maze[ny][nx]!='#':
                dist[ny][nx]=dist[y][x]+1
                q.append([ny,nx])
    return max([max(i) for i in dist])

h,w=map(int,input().split())
a=[input() for _ in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
for sy in range(h):
    for sx in range(w):
        if a[sy][sx]!='#':
            ans=max(ans,bfs(a,h,w,sy,sx))
print(ans)

import queue
import numpy as np

H, W = list(map(int, input().split()))
maze = [list(input()) for _ in range(H)]
dir4 = [[-1,0],[1,0],[0,-1],[0,1]]


def solveMaze(s):
    q = queue.Queue()
    q.put([s[0],s[1],0])
    times = [[999999999 for j in range(W)] for i in range(H)]
    tmpAns = 0
    times[s[0]][s[1]] = 0
    while not q.empty():
        now = q.get()
        tmpAns = max(tmpAns, now[2])
        for i in range(4):
            nextH = now[0] + int(dir4[i][0])
            nextW = now[1] + int(dir4[i][1])
            nextTime = now[2] + 1

            if nextH < 0 or nextH >= H or nextW < 0 or nextW >=W or maze[nextH][nextW] == "#" or times[nextH][nextW] <= nextTime:
                continue
            else:
                times[nextH][nextW] = nextTime
                q.put([nextH, nextW, nextTime])

    return tmpAns


ans = 0

for sH in range(H):
    for sW in range(W):
        if maze[sH][sW] == ".":
            ans = max(ans, solveMaze([sH, sW]))

print(ans)







import sys
from collections import deque

H,W=list(map(int,input().split()))
S=list(sys.stdin)

ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]=='#':
            continue
        dist=[[-1]*W for _ in range(H)]
        dist[i][j]=0
        que=deque()
        que.append((i,j))
        while que:
            i,j=que.popleft()
            ans=max(ans,dist[i][j])
            for ni,nj in (i-1,j),(i,j+1),(i+1,j),(i,j-1):
                if 0<=ni<H and 0<=nj<W and S[ni][nj]=='.' and dist[ni][nj]==-1:
                    dist[ni][nj]=dist[i][j]+1
                    que.append((ni,nj))

print(ans)


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

# In[1]:


from collections import deque


# In[2]:


H,W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(input())


# In[3]:


def bfs(sx,sy):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    d = [[-1]*W for _ in range(H)]
    q = deque([])
    q.append([sx,sy])
    d[sx][sy] = 0
    ans = 0
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != "#" and d[nx][ny] == -1:
                q.append([nx,ny])
                d[nx][ny] = d[x][y] + 1
                ans = max(ans,d[nx][ny])
    return ans


# In[5]:


ans = 0
for sh in range(H):
    if "." in S[sh]:
        for sw in range(W):
            if S[sh][sw] == ".":
                ans = max(ans,bfs(sh,sw))
print(ans)


# In[ ]:






from copy import deepcopy  

H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
ans = 0
queue = [[1,0],[-1,0],[0,1],[0,-1]]

def now(n,s):
    t = []
    for i in queue:
        j = n[0] + i[0]
        k = n[1] + i[1]
        if 0 <= j < H and 0 <= k < W:
            if s[j][k] == ".":
                t.append([j,k])
                s[j][k] = "#"
    return [t,s]
        

def bfs(trust, a, s):
    t = []
    for i in trust:
        tt, s = now(i,s)
        t += tt
    if len(t) == 0:
        return a
    else:
        a = a + 1
        return bfs(t, a, s)


for i in range(H):
    for j in range(W):
        s = deepcopy(S)
        if S[i][j] == ".":
            s[i][j] = "#"
            ans = max(ans, bfs([[i,j]], 0, s))
print(ans)

import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
  H,W = i_map()
  S = [input() for i in range(H)]
  dy_dx=[[1,0],[0,1],[-1,0],[0,-1]]
  ans = 0

  for sy in range(H):
        for sx in range(W):
            if S[sy][sx] == "#":
                continue

            dist=[[-1 for _ in range(W)] for _ in range(H)]
            dist[sy][sx] = 0
            d = deque()
            d.append([sx,sy])
            while d:
              nx, ny = d.popleft()
              for dy,dx in dy_dx:
                    y,x = ny+dy,nx+dx
                    if 0<=y<H and 0<=x<W and S[y][x] != "#" and dist[y][x] == -1:
                        dist[y][x] = dist[ny][nx] + 1
                        d.append([x,y])
            
            ans = max(ans, max(list(itertools.chain.from_iterable(dist))))
  print(ans)

 
 
def __starting_point():
    main()
__starting_point()

from queue import deque

H, W = map(int,input().split())
S = list(list(input()) for _ in range(H))
ans = 0

for h in range(H):
  for w in range(W):
    if S[h][w] == ".":
      D = [[-1] * W for _ in range(H)]
      D[h][w] = 0
      Q = deque()
      Q.append((h, w))
      
      while Q:
        y, x = Q.popleft()

        for i, j in (1, 0), (-1, 0), (0, 1), (0, -1):
          y2, x2 = y + i, x + j

          if 0 <= y2 < H and 0 <= x2 < W and S[y2][x2] == "." and D[y2][x2] == -1:
            Q.append((y2, x2))
            D[y2][x2] = D[y][x] + 1

      for i in range(H): ans = max(ans, max(D[i]))

print(ans)

from collections import deque
import numpy as np
def main():
    H,W = map(int,input().split())
    maze = [input() for _ in range(H)]

    ans = 0
    for x in range(H):
        for y in range(W):
            #壁からはスタートできない
            if maze[x][y] == "#":
                continue

            #初期化
            distance = [[0]*W for _ in range(H)]
            #start位置
            stack = deque([[x,y]])

            while stack:
                h,w = stack.popleft()
                for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                    new_h, new_w = h+i, w+j
                    if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                        continue
                    elif maze[new_h][new_w] != '#' and distance[new_h][new_w] == 0:
                        distance[new_h][new_w] = distance[h][w] + 1
                        stack.append([new_h, new_w])

            distance[x][y] = 0
            ans = max(ans, np.max(distance))

    print(ans)

main()


import sys

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

def resolve():
    def bfs(sy, sx):
        q = deque()
        q.append((sy, sx))
        dist = [[-1] * (W + 2) for _ in range(H + 2)]
        dist[sy][sx] = 0
        drc = [(-1, 0), (0, 1), (1, 0), (0, -1)]

        while q:
            sy, sx = q.popleft()
            for dy, dx in drc:
                ny = dy + sy
                nx = dx + sx
                if G[ny][nx] == "." and dist[ny][nx] == -1:
                    dist[ny][nx] = dist[sy][sx] + 1
                    q.append((ny, nx))

            if not q:
                return dist[sy][sx]

    H, W = list(map(int, input().split()))
    G = []
    G.append(["#"] * (W + 2))
    G += [["#"] + list(input()) + ["#"] for _ in range(H)]
    G.append(["#"] * (W + 2))

    ans = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if G[i][j] == "#":
                continue
            ans = max(ans, bfs(i, j))
            
    print(ans)


def __starting_point():
    resolve()

__starting_point()

from collections import deque
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]

ans = 0
for sh in range(H):
    for sw in range(W):
        if maze[sh][sw] == "#":
            continue
        dist = [[-1] * W for _ in range(H)]
        dist[sh][sw] = 0
        que = deque([[sh, sw]])

        while que:
            nh, nw = que.pop()
            for dh, dw in directions:
                tmp_h, tmp_w = nh + dh, nw + dw
                if not ((0 <= tmp_h < H) and (0 <= tmp_w < W)):
                    continue
                if maze[tmp_h][tmp_w] == "#":
                    continue
                if dist[tmp_h][tmp_w] != -1:
                    continue

                dist[tmp_h][tmp_w] = dist[nh][nw] + 1
                que.appendleft([tmp_h, tmp_w])

        ans = max(ans, max([max(d) for d in dist]))

print(ans)

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

maze = []
maze.append(['#']*(W+2))
for i in range(H):
  line = input()
  line_n = ['#']+[line[i] for i in range(W) ]+['#']
  maze.append(line_n)
maze.append(['#']*(W+2))
for i in range(H+2):
  for j in range(W+2):
    if maze[i][j]=='#':
      maze[i][j]=9
maze_copy = copy.deepcopy(maze)
global_max = 0
for i in range(1,H+1):
  for j in range(1,W+1):
    maze = copy.deepcopy(maze_copy)
    sx = i
    sy = j
    if maze[i][j]!=9:
      pos = [[sx,sy,0]]
      max_depth = 0
      while len(pos)>0:
        x,y,depth = pos.pop(0)
        #print(x,y)
        if depth >max_depth:
          max_depth = depth
        ##探索終了条件
        maze[x][y] = 0
        if maze[x-1][y]=='.':
            pos.append([x-1,y,depth+1])
            maze[x-1][y] = 0
        if maze[x][y-1]=='.':
            pos.append([x,y-1,depth+1])
            maze[x][y-1] = 0
        if maze[x+1][y]=='.':
            pos.append([x+1,y,depth+1])
            maze[x+1][y] = 0
        if maze[x][y+1]=='.':
            pos.append([x,y+1,depth+1])
            maze[x][y+1] = 0
      #print("max_depth={}".format(max_depth))
      if max_depth> global_max:
        global_max = max_depth
print(global_max)

from collections import *
from copy import *
H,W = map(int,input().split())
S = [(W+2)*["#"]]+[["#"]+list(input())+["#"] for h in range(H)]+[(W+2)*["#"]]
D = [[1,0],[-1,0],[0,1],[0,-1]]
ans = 0
P = deque([])
Q = deque([])

for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]==".":
      P+=[[h,w]]

while P:
  T = deepcopy(S)
  sx,sy = P.popleft()
  T[sx][sy] = 0
  Q = deque([[sx,sy]])
  while Q:
    x,y = Q.popleft()
    for dx,dy in D:
      if T[x+dx][y+dy]==".":
        T[x+dx][y+dy] = T[x][y]+1
        Q+=[[x+dx,y+dy]]
        ans = max(ans,T[x+dx][y+dy])

print(ans)

from collections import *
from copy import *
H,W = map(int,input().split())
S = [(W+2)*["#"]]+[["#"]+list(input())+["#"] for h in range(H)]+[(W+2)*["#"]]
D = [[1,0],[-1,0],[0,1],[0,-1]]
ans = 0
P = deque([])
Q = deque([])
 
for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]==".":
      P+=[[h,w]]
 
while P:
  T = deepcopy(S)
  sx,sy = P.popleft()
  T[sx][sy] = 0
  Q = deque([[sx,sy]])
  while Q:
    x,y = Q.popleft()
    for dx,dy in D:
      if T[x+dx][y+dy]==".":
        T[x+dx][y+dy] = T[x][y]+1
        Q+=[[x+dx,y+dy]]
        ans = max(ans,T[x+dx][y+dy])
 
print(ans)

# -*- coding: utf-8 -*-
"""
Created on Tue Sep  8 18:25:14 2020

@author: liang
"""

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

field = [input() for i in range(H)]

def Init():
    return [[-1]*W for _ in range(H)]

ans = -1

from collections import deque
q = deque()
adj = ((1,0), (-1,0), (0,1), (0,-1))
def BFS(y,x):
    def isValid(t):
        if t[0] < 0 or t[0] >= H or t[1] < 0 or t[1] >= W or field[t[0]][t[1]] == "#":
            return False
        return True
    d = Init()
    if field[y][x] == '#':
        return -1
    d[y][x] = 0
    q.append((y,x))
    res = 0
    while q:
        cur = q.popleft()
        for a in adj:
            nex = (cur[0]+a[0], cur[1]+a[1])
            if isValid(nex) and (d[nex[0]][nex[1]]== -1 or d[nex[0]][nex[1]] > d[cur[0]][cur[1]]+1):
                d[nex[0]][nex[1]] = d[cur[0]][cur[1]]+1
                #if res < d[nex[0]][nex[1]]:
                #    res = d[nex[0]][nex[1]]
                res = max(res, d[nex[0]][nex[1]])
                q.append(nex)
    return res

for i in range(H):
    for j in range(W):
        tmp = BFS(i,j)
        if tmp > ans:
            ans = tmp
print(ans)

H, W = map(int,input().split())
s = [list(input()) for j in range(H)]

def bfs(h, w):
    checked = [[False for i in range(W)] for j in range(H)]
    q = [(h, w, 0)] if s[h][w] == '.' else []
    checked[h][w] = True
    g_n = 0
    while q:
        h_, w_, n = q.pop(0)
        g_n = max(n, g_n)
        for i, j in zip([0,0,-1,1],[-1,1,0,0]):
            if (0 <= h_+i < H) and (0 <= w_+j < W):
                if checked[h_+i][w_+j]: continue
                checked[h_+i][w_+j] = True
                if s[h_+i][w_+j] == '.': q.append((h_+i, w_+j, n+1))
    return g_n

n = 0
for i in range(H):
    for j in range(W):
        n = max(n, bfs(i,j))

print(n)

from copy import deepcopy
from collections import deque
from itertools import product
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid]) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def longest_path(grid, root):
    def restore_path(prev, p):
        A = deque()
        while p:
            A.appendleft(p)
            p = prev[p]
        return list(A)
    
    x, y = root
    prev = {root:None}
    grid[y, x] = '!'
    queue = deque([root])
    while queue:
        x, y = queue.popleft()
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'sg.':
                prev[nx, ny] = x, y
                queue.append((nx, ny))
                grid[ny, nx] = '!'
    return restore_path(prev, (x, y))

h, w = map(int, input().split())
grid = Grid([input() for s in range(h)])
ans = 0
for y, x in product(range(h), range(w)):
    if grid[y, x] == '.':
        path = longest_path(deepcopy(grid), (x, y))
        ans = max(ans, len(path)-1)
print(ans)

import queue
h,w = map(int,input().split())
v = [(1, 0), (0, 1), (-1, 0), (0, -1)]
s = [input() for i in range(h)]

ans = 0
que = queue.Queue()
for i in range(h * w):
    c = 0
    d = [[h*w] * w for i in range(h)]
    p = (i//w, i%w)
    if s[p[0]][p[1]] == '#':
        continue
    d[p[0]][p[1]] = 0
    que.put(p)
    while not que.empty():
        y,x = que.get()
        c = d[y][x]
        for dy, dx in v:
            yy = y + dy
            xx = x + dx
            if yy < 0 or xx < 0 or h <= yy or w <= xx:
                continue
            if s[yy][xx] == '#':
                continue
            if d[yy][xx] < h*w:
                continue
            que.put((yy, xx))
            d[yy][xx] = c + 1
    ans = max(ans, c)
print(ans)

from collections import deque

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

field = []
for i in range(H):
    field.append(input())

conn = [[[] for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            for e in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                h, w = i + e[0], j + e[1]
                if 0 <= h < H and 0 <= w < W and field[h][w] == '.':
                    conn[i][j].append([h, w])
d = 0
for i in range(H):
    for j in range(W):
        l = 0
        q = deque([[i, j]])
        dist = [[-1 for _ in range(W)] for _ in range(H)]
        dist[i][j] = 0
        while q:
            v = q.popleft()
            for w in conn[v[0]][v[1]]:
                if dist[w[0]][w[1]] == -1:
                    q.append(w)
                    dist[w[0]][w[1]] = dist[v[0]][v[1]] + 1
                    l = dist[w[0]][w[1]]

        d = max(d, l)

print(d)

from copy import deepcopy
from collections import deque
h,w = map(int,input().split())
s = [['#']*(w+2) for i in range(h+2)]
for i in range(h):
    x = input()
    for j in range(w):
        s[i+1][j+1] = x[j]
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j] != '#':
            maze = deepcopy(s)
            maze[i][j] = 0
            queue = deque([[i,j]])
            while queue:
                x,y = queue.popleft()
                for a,b in([0,-1],[0,1],[1,0],[-1,0]):
                    nh,nw = x+a,y+b
                    if maze[nh][nw] == '.':
                        maze[nh][nw] = maze[x][y] + 1
                        queue.append([nh,nw])
            l = 0
            for x in range(1,h+1):
                for y in range(1,w+1):
                    if maze[x][y] != '#':
                        l = max(l,maze[x][y])
            ans = max(ans,l)
print(ans)

from collections import deque
h,w=list(map(int,input().split()))

s=[]
s.append(list("#"*(w+2)))
start=[]
for i in range(1,h+1):
  wk=list("#"+input()+"#")
  for j in range(1,w+1):
    if wk[j]==".":
      start.append([i,j])
  s.append(wk)
s.append(list("#"*(w+2)))

dist=[[-1]*(w+2) for _ in range(h+2)]

def bfs(start):
  que=deque([start])
  dist[start[0]][start[1]]=0
  end=[]
  cnt=0
  while que:
    y,x=que.popleft()
    for py,px in [(1,0),(-1,0),(0,1),(0,-1)]:
      ny,nx=y+py,x+px
      if s[ny][nx]=="." and dist[ny][nx]==-1:
        dist[ny][nx]=dist[y][x]+1
        que.append([ny,nx])
        cnt=max(cnt,dist[y][x]+1)
  return cnt

ans=0
for i in start:
  ans=max(ans,bfs(i))
  dist=[[-1]*(w+2) for _ in range(h+2)]
print(ans)


from collections import deque
import numpy as np

H,W = map(int,input().split())
maze = [input() for _ in range(H)]

ans = 0
for x in range(H):
    for y in range(W):
        #壁からはスタートできない
        if maze[x][y] == "#":
            continue

        distance = [[-1]*W for _ in range(H)]
        distance[x][y] = 0
        #start位置
        stack = deque([[x,y]])

        while stack:
            h,w = stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h, new_w = h+i, w+j
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue
                elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == -1:
                    distance[new_h][new_w] = distance[h][w]+1
                    stack.append([new_h, new_w])

        ans = max(ans, np.max(distance))

print(ans)

from collections import deque
 
H,W=map(int,input().split())
S=[input() for _ in range(H)]
ans=0
d=deque([])
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    d.append((i,j,0))
    visited=[[-1]*W for _ in range(H)]
    visited[i][j]=0
    while d:
      x,y,c=d.popleft()
      for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and visited[nx][ny]==-1 and S[nx][ny]=='.':
          visited[nx][ny]=c+1
          d.append((nx,ny,c+1))
    ans=max(ans,c)
print(ans)

from collections import *
from copy import *
H,W = map(int,input().split())
S = [(W+2)*["#"]]+[["#"]+list(input())+["#"] for h in range(H)]+[(W+2)*["#"]]
D = [[1,0],[-1,0],[0,1],[0,-1]]
ans = 0
P = deque([])
Q = deque([])
 
for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]==".":
      P+=[[h,w]]
 
while P:
  T = deepcopy(S)
  sx,sy = P.popleft()
  T[sx][sy] = 0
  Q = deque([[sx,sy]])
  while Q:
    x,y = Q.popleft()
    for dx,dy in D:
      if T[x+dx][y+dy]==".":
        T[x+dx][y+dy] = T[x][y]+1
        Q+=[[x+dx,y+dy]]
        ans = max(ans,T[x+dx][y+dy])
 
print(ans)

from collections import deque
import copy

H,W=map(int,input().split())
MAP=[list(input()) for y in range(H)]

def Maze(_x, _y):
  MAP2=copy.deepcopy(MAP)
  q=deque([[_x,_y]])
  MAP2[_y][_x]=0
  while q:
    xy=q.popleft()
    for d in [(0,-1),(-1,0),(0,1),(1,0)]:
      x2,y2=xy[0]+d[0],xy[1]+d[1]
      if x2<0 or y2<0 or x2>=W or y2>=H:
        continue
      if MAP2[y2][x2]=='.':
        q.append([x2,y2])
        MAP2[y2][x2]=MAP2[xy[1]][xy[0]]+1
  
  maxM=0
  for y in range(H):
    for x in range(W):
      if type(MAP2[y][x])==int:
        maxM=max(maxM, MAP2[y][x])
  return maxM
  

ans=0
for y in range(H):
  for x in range(W):
    if MAP[y][x]=='.':
      ans=max(ans, Maze(x,y))
print(ans)

import queue

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

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

ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            seen=[[0 for _ in range(w)] for _ in range(h)]
            length=[[0 for _ in range(w)] for _ in range(h)]
            q=queue.Queue()
            q.put([i,j])
            seen[i][j]=1
            while not q.empty():
                ci,cj=q.get()
                for ni,nj in [[ci-1,cj],[ci+1,cj],[ci,cj-1],[ci,cj+1]]:
                    if 0<=ni<h and 0<=nj<w and s[ni][nj]=="." and seen[ni][nj]==0:
                        q.put([ni,nj])
                        length[ni][nj]=length[ci][cj]+1
                        seen[ni][nj]=1
            ans=max(ans,length[ci][cj])

print(ans)

from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)] #マップ
vi=[ [-1 for _ in range(w)] for _ in range(h)]#visit
st=deque()

d=[[0,1],[-1,0],[1,0],[0,-1]]

mx=0

for i in range(h):
  for j in range(w):
    vi=[ [-1 for _ in range(w)] for _ in range(h)]
    st.append([i,j,0])
    
    while st:
      h1,w1,k=st.popleft()

      if 0<=h1<h and 0<=w1<w and vi[h1][w1]==-1 and s[h1][w1]==".":
        vi[h1][w1]=k
        for m in d:
          st.append([h1+m[0],w1+m[1],k+1])
    for m in vi:
      mx=max(mx,max(m))

print(mx)

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import copy
from collections import deque

def yn(b):
    print(("Yes" if b==1 else "No"))
    return

def sagasu(h,w,mp,sh,sw):
    d = deque()
    x=sw
    y=sh
    d.append([y,x,0])
    while len(d)>0:
        y,x,cnt=d.popleft()
        if mp[y][x]==-2 or mp[y][x] > cnt:
            mp[y][x]=cnt
            nxt=[[y-1,x],[y+1,x],[y,x-1],[y,x+1]]
            for nx in nxt:
                y2=nx[0]
                x2=nx[1]
                if y2 < 0:
                    continue
                if y2 >= h:
                    continue
                if x2 < 0:
                    continue
                if x2 >= w:
                    continue
                if mp[y2][x2] == -2 or mp[y2][x2] > cnt:
                    d.append([y2,x2,cnt+1])
    ret=-1
    for y in range(h):
        for x in range(w):
            ret=max(ret,mp[y][x])
    return ret
def resolve():
    readline=sys.stdin.readline

    h,w=list(map(int, readline().rstrip().split()))

    mp=[[0 for i in range(w)] for j in range(h)]
    for y in range(h):
        ss=readline().rstrip()
        for x in range(w):
            if ss[x]=="#":
                mp[y][x]=-1 #kabe
            else:
                mp[y][x]=-2 #miti
    ans=0
    for y in range(h):
        for x in range(w):
            if mp[y][x]==-2:
                mp2=copy.deepcopy(mp)
                n=sagasu(h,w,mp2,y,x)
                ans=max(ans,n)
    print(ans)
    
    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    return

### ----------------
### ここまで 
### ----------------


from collections import deque
import _pickle as cPickle
import cProfile
h, w = map(int, input().split())
s = [["#"]*(w+2)] + [["#"]+list(input())+["#"] for i in range(h)] + [["#"]*(w+2)]
ans = 0
A=list()
for i in range(1, h+1):
    for j in range(1, w+1):
        t=cPickle.loads(cPickle.dumps(s, -1))
        c=dict()
        A=list()
        if s[i][j] == "#":
            continue
        a = deque([[i, j, 0]])
        while len(a) > 0:
            x, y, cnt = a.popleft()
            t[x][y] = "#"
            if t[x-1][y] == ".":
                if [x-1, y, cnt+1] not in A:
                  a.append([x-1, y, cnt+1])
                  A.append([x-1, y, cnt+1])
            if t[x+1][y] == ".":
                if [x+1, y, cnt+1] not in A:
                  a.append([x+1, y, cnt+1])
                  A.append([x+1, y, cnt+1])
            if t[x][y-1] == ".":
                if [x, y-1, cnt+1] not in A:
                  a.append([x, y-1, cnt+1])
                  A.append([x, y-1, cnt+1])
            if t[x][y+1] == ".":
                if [x, y+1, cnt+1] not in A:
                  a.append([x, y+1, cnt+1])
                  A.append([x, y+1, cnt+1])
        ans = max(ans, cnt)
print(ans)

# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
MOD = int(1e9)+7
INF = float('inf')


def solve():
    n, m = [int(x) for x in input().split()]
    a = []
    starts = []
    for i in range(n):
        a.append(input())
        for j in range(m):
            if a[i][j] == '.':
                starts.append((i, j))

    def bfs(v):
        q = deque([(v, 0)])
        mx = 0
        mv = v
        w = defaultdict(int)
        w[v] = 1
        while q:
            v, d = q.popleft()
            if d > mx:
                mv = v
                mx = d
            i, j = v
            for x, y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                if 0 <= i + x < n and 0 <= j + y < m and not w[(i+x,j+y)] and a[i+x][j+y] == '.':
                    w[(i+x,j+y)] = 1
                    q.append(((i+x, j+y), d + 1))
            

        return mx, mv

    ans = 0
    for start in starts:
        _, start = bfs(start)
        cur, start = bfs(start)

        ans = max(ans, cur)
    print(ans)


    

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""
1
4
-1 1 1 -1

"""


from collections import deque
H, W = map(int, input().split())
L = []
for _ in range(H):
    s = input()
    a = []
    for i in range(len(s)):
        a.append(s[i])
    L.append(a)

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]


def bfs(x, y):
    dp = [[10000000] * W for _ in range(H)]
    dp[y][x] = 0
    if L[y][x] == '#':
        return dp
    else:
        d = deque()
        d.append([x, y])
        while len(d) > 0:
            s = d.popleft()
            for i in range(4):
                if (s[1] +
                    dy[i] >= 0 and s[1] +
                    dy[i] < H and s[0] +
                    dx[i] >= 0 and s[0] +
                        dx[i] < W):
                    if L[s[1] +
                         dy[i]][s[0] +
                                dx[i]] == '.' and dp[s[1] +
                                                     dy[i]][s[0] +
                                                            dx[i]] == 10000000:
                        d.append([s[0] + dx[i], s[1] + dy[i]])
                        dp[s[1] + dy[i]][s[0] + dx[i]] = dp[s[1]][s[0]] + 1

        return dp


max_num = 0
for i in range(H):
    for j in range(W):
        dp = bfs(j, i)
        for k in dp:
            for p in k:
                if (p == 10000000):
                    continue
                max_num = max(max_num, p)
print(max_num)

from collections import deque
import copy

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]

def bfs(x,y):
    check = copy.deepcopy(S)
    que = deque()
    que.append((x,y))
    check[y][x] = 0
    while que.__len__() != 0:
        x,y = que.popleft()
        tmp = check[y][x]
        for dx,dy in (1,0),(-1,0),(0,1),(0,-1):
            sx = x + dx
            sy = y + dy
            if -1 < sx < W and -1 < sy < H:
                if check[sy][sx] == '.':
                    check[sy][sx] = tmp + 1
                    que.append((sx,sy))
    return tmp

ans = 0
for x in range(W):
    for y in range(H):
        if S[y][x] == '.':
            ans = max(bfs(x,y),ans)

print(ans)

from collections import deque
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]

ans = 0
for sh in range(H):
    for sw in range(W):
        if maze[sh][sw] == "#":
            continue

        dist = [[-1] * W for _ in range(H)]
        dist[sh][sw] = 0
        que = deque([[sh, sw]])

        while que:
            nh, nw = que.pop()
            for dh, dw in direction:
                if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
                    continue
                if maze[nh + dh][nw + dw] == "#":
                    continue
                if dist[nh + dh][nw + dw] != -1:
                    continue

                dist[nh + dh][nw + dw] = dist[nh][nw] + 1
                que.appendleft([nh + dh, nw + dw])

        ans = max(ans, max([max(d) for d in dist]))

print(ans)

from collections import deque
import numpy as np
H, W = map(int,input().split())
maze = [input() for _ in range(H)]

dxy =[[1,0],[0,1],[-1,0],[0,-1]]

ans = 0
for x in range(H):
    for y in range(W):
        if maze[x][y]=="#":
            continue
            
        seen = [[0]*W for _ in range(H)]
        que = deque([[x,y]])

        while que:
            vx,vy = que.popleft()
            for i,j in dxy:
                next_x,next_y = vx+i,vy+j
                if not(0<= next_x < H) or not(0<= next_y <W):
                    continue
                elif maze[next_x][next_y] !="#" and seen[next_x][next_y]==0:
                    seen[next_x][next_y]=seen[vx][vy]+1
                    que.append([next_x,next_y])
        seen[x][y] = 0
        ans = max(ans,np.max(seen))
print(ans)

from collections import deque
from typing import List


def main():
    h, w = list(map(int, input().split()))
    g = []
    for _ in range(h):
        r = list(input())
        g.append(r)
    print((mm(h, w, g)))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            v = set()
            q = deque([(i, j, 0)])
            v.add((i, j))
            while q:
                ii, jj, cnt = q.popleft()
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and (ii + 1, jj) not in v:
                    q.append((ii + 1, jj, cnt + 1))
                    v.add((ii + 1, jj))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and (ii, jj + 1) not in v:
                    q.append((ii, jj + 1, cnt + 1))
                    v.add((ii, jj + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and (ii - 1, jj) not in v:
                    q.append((ii - 1, jj, cnt + 1))
                    v.add((ii - 1, jj))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and (ii, jj - 1) not in v:
                    q.append((ii, jj - 1, cnt + 1))
                    v.add((ii, jj - 1))
    return ret


def __starting_point():
    main()

__starting_point()

H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(input())

def bfs(start):
    already = {}
    queue = []
    counter = 0
    queue.append((start[0], start[1], 0))
    already[start] = True
    max_depth = 0
    while counter < len(queue):
        y, x, depth = queue[counter]
        if depth > max_depth:
            max_depth = depth
        for move in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            new_y = y + move[0]
            new_x = x + move[1]
            if new_y >= 0 \
            and new_y < H \
            and new_x >= 0 \
            and new_x < W \
            and S[new_y][new_x] == '.' \
            and (new_y, new_x) not in already:
                already[(new_y, new_x)] = True
                queue.append((new_y, new_x, depth+1))
        counter += 1
    return max_depth

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        depth = bfs((i, j))
        if answer < depth:
            answer = depth
print(answer)

from collections import deque
H, W = map(int, input().split())
S = [''] * H
for i in range(H):
    S[i] = input()
dests = ((-1, 0), (0, -1), (1, 0), (0, 1))

def maze(sx, sy):
    d = deque()
    dist = [[-1] * W for i in range(H)]
    dist[sx][sy] = 0
    d.append((sx, sy))
    while True:
        x, y = d.popleft()
        for dest in dests:
            nx, ny = x + dest[0], y + dest[1]
            if nx >= 0 and nx < H and ny >= 0 and ny < W and S[nx][ny] == '.' and dist[nx][ny] == -1:
                d.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1
        if not d: return dist[x][y]

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#': continue
        ans = max(ans, maze(i, j))
print(ans)

def main():
	H, W = [int(x) for x in input().split(" ")]
	S = []
	S.append(["X"] * (W + 2))
	h = 0
	w = 0
	for i in range(H):
		row = list(input())
		S.append(["X"] + row + ["X"])
		if not h and not w and row.count(".") > 0:
			h = i + 1
			w = row.index(".") + 1
	S.append(["X"] * (W + 2))

	ans = []
	for i in range(H):
		for j in range(W):
			ans.append(BFS(S, i + 1, j + 1, H + 2, W + 2))
	print((max(ans)))

def BFS(M, i, j, H, W):
	if M[i][j] != ".":
		return 0
	to_visit = [{"row": i, "col": j, "step": 0}]
	checked = [[0] * W for x in range(H)]
	checked[i][j] = 1
	z = [[0] * W for x in range(H)]
	while len(to_visit):
		visiting = to_visit.pop(0)
		r0 = visiting["row"]
		c0 = visiting["col"]
		s0 = visiting["step"]
		z[r0][c0] = s0
		for d in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
			r = r0 + d[0]
			c = c0 + d[1]
			s = s0 + 1
			if checked[r][c] == 0 and M[r][c] == ".":
				to_visit.append({"row": r, "col": c, "step": s})
				checked[r][c] = 1
	a = 0
	for i in range(len(z)):
		for j in range(len(z[i])):
			if a < z[i][j]:
				a = z[i][j]
	return a

main()


# -*- coding: utf-8 -*-
"""
Created on Tue Sep  8 18:25:14 2020

@author: liang
"""

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

field = [input() for i in range(H)]

def Init():
    return [[-1]*W for _ in range(H)]

ans = -1

from collections import deque
q = deque()
adj = ((1,0), (-1,0), (0,1), (0,-1))
def BFS(y,x):
    def isValid(t):
        if t[0] < 0 or t[0] >= H or t[1] < 0 or t[1] >= W or field[t[0]][t[1]] == "#":
            return False
        return True
    d = Init()
    if field[y][x] == '#':
        return -1
    d[y][x] = 0
    q.append((y,x))
    res = 0
    while q:
        cur = q.popleft()
        for a in adj:
            nex = (cur[0]+a[0], cur[1]+a[1])
            if isValid(nex) and (d[nex[0]][nex[1]]== -1 or d[nex[0]][nex[1]] > d[cur[0]][cur[1]]+1):
                d[nex[0]][nex[1]] = d[cur[0]][cur[1]]+1
                if res < d[nex[0]][nex[1]]:
                    res = d[nex[0]][nex[1]]
                q.append(nex)
    return res

for i in range(H):
    for j in range(W):
        tmp = BFS(i,j)
        if tmp > ans:
            ans = tmp
print(ans)

import math
import sys
sys.setrecursionlimit(10000)
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(str(input()))
  
def main(l, d, cnt):
  tmp = []
  for n in l:
    i, j = n[0], n[1]
    if (0<i) and (S[i-1][j] == '.'):
      if d[i-1][j] > d[i][j]+1:
        d[i-1][j] = d[i][j]+1
        tmp.append([i-1, j])
    if (i<H-1) and (S[i+1][j] == '.'):
      if d[i+1][j] > d[i][j]+1:
        d[i+1][j] = d[i][j]+1
        tmp.append([i+1, j])
    if (0<j) and (S[i][j-1] == '.'):
      if d[i][j-1] > d[i][j]+1:
        d[i][j-1] = d[i][j]+1
        tmp.append([i, j-1])
    if (j<W-1) and (S[i][j+1] == '.'):
      if d[i][j+1] > d[i][j]+1:
        d[i][j+1] = d[i][j]+1
        tmp.append([i, j+1])
  if tmp == []:
    return cnt
  else:
    cnt += 1
    return main(tmp, d, cnt)
  
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '.':
      d = [[float('inf') for i in range(W)] for j in range(H)]
      d[i][j] = 0
      cnt = main([[i, j]], d, 0)
      ans = max(ans, cnt)
print(ans)

import collections # deque, Counter
# import itertools   # accumulate, compress, permutations(nPr), combinations(nCr)
# import bisect      # bisect_left(insert位置), bisect_right(slice用)
# import math        # factorical（階乗) # hypot(距離)
# import heapq
# from fractions import gcd # Python3.5以前 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # Python3.6以降
# --------------------------------------------------------------

H,W   = map(int,input().split())
maze  = [[None for _ in range(W)] for _ in range(H)]

for i in range(H):
    maze[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

cnt = 0

for j in range(H):
    for k in range(W):
            if maze[j][k]=='#':
                continue
            else:
                sy = j
                sx = k

                seen = [[-1 for _ in range(W)] for _ in range(H)]
                seen[sy][sx] = 0

                que  = collections.deque()  # 発見済未訪問な頂点
                que.append([sy,sx])

                while(len(que)!=0):
                    p = que.popleft()
                    for i in range(4):
                        ny = p[0] + dy[i]
                        nx = p[1] + dx[i]
                        if (ny >= 0 and nx >=0 and ny < H and nx < W and seen[ny][nx] == -1 and maze[ny][nx] != '#'):
                            seen[ny][nx] = seen[p[0]][p[1]] + 1
                            que.append([ny,nx])

                cnt = max(cnt, max([x for row in seen for x in row]))

print(cnt)

from collections import deque


def main():
    row, col = list(map(int, input().split()))
    S = [list(input()) for _ in range(row)]
    ans = 0

    for r in range(row):
        for c in range(col):
            if S[r][c] == "#":
                continue
            q = deque()
            q.append((r, c))
            dist = [[-1 for _ in range(col)] for _ in range(row)]
            dist[r][c] = 0

            while q:
                r, c = q.popleft()
                for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    nr, nc = r + dr, c + dc
                    if not(0 <= nr < row and 0 <= nc < col):
                        continue
                    if S[nr][nc] == "#":
                        continue
                    if dist[nr][nc] != -1:
                        continue
                    q.append((nr, nc))
                    dist[nr][nc] = dist[r][c] + 1
                    ans = max(ans, dist[nr][nc])

    print(ans)


def __starting_point():
    main()

__starting_point()

import collections
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

H, W, *S = open(0).read().split()
H, W = [int(_) for _ in [H, W]]
A = []
B = []
C = []
for i in range(H * W):
    x, y = divmod(i, W)
    if S[x][y] == '.':
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '.':
                A += [i]
                B += [nx * W + ny]
                C += [1]
F = floyd_warshall(csr_matrix((C, (A, B)), shape=(H*W, H*W)))
print((int(np.max(F[F!=np.inf]))))


from copy import deepcopy
from collections import Counter, defaultdict, deque
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]
def maze_solve(S_1,S_2,maze_list):
    d = deque()
    dist[S_1][S_2] = 0
    d.append([S_1,S_2])
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    while d:
        v = d.popleft()
        x = v[0]
        y = v[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
    return max(list(map(lambda x: max(x), dist)))
h,w = MI()
ans = 0
maze = [list(input()) for _ in range(h)]
dist = [[-1]*w for _ in range(h)]
start_list = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
          dist[i][j] = 0
        else:
          start_list.append([i,j])
dist_copy = deepcopy(dist)
for k in start_list:
  dist = deepcopy(dist_copy)
  ans = max(ans,maze_solve(k[0],k[1],maze))
print(ans)

#import sys
#input=sys.stdin.readline()
#print(input)

#import pprint
h,w = map(int,input().split())
s = [list(input())for i in range(h)]
#print("s")
#pprint.pprint(s,width=w*10)

visited = [[0 for i in range(w)] for j in range(h)]#sと同じ形に0を配置した表
quene = []#移動元Nowとなることができる座標のリスト
ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            quene.append([i,j])#スタート地点をQueneに追加
            visited[i][j]=1#スタート地点を1にする
#            print("visited")
#            pprint.pprint(visited,width=w*10)
#            print(quene)

            dy_dx=[[1,0],[-1,0],[0,1],[0,-1]]#１回に移動出来る量

            while len(quene)>=1:
                now=quene.pop(0)#queneの左端の項を取り出す
#                print(now)
                for k in range(4):
                    y=now[0]+dy_dx[k][0]#nowから移動先[x,y]へのy軸方向の移動量
                    x=now[1]+dy_dx[k][1]#nowから移動先[x,y]へのx軸方向の移動量
                    if 0<=y<h and 0<=x<w:#移動先が表を飛び出していなければOK
                        if s[y][x]!="#" and visited[y][x]==0:#移動先が壁でない、かつ行ったことがなければOK
                            visited[y][x]=visited[now[0]][now[1]]+1#移動先の値をNowの値+1にする
                            quene.append([y,x])#Queneに移動先座標を追加
#                           pprint.pprint(visited,width=w*10)
#       一つのスタート地点から幅優先探索を終わらせたら、移動量の最大値を求める
        for l in range(h):
            for m in range(w):
                ans = max(ans,visited[l][m])#これまでの最大値と今回得られた移動量の最大値を比較し、大きいほうを新しい答えにする
        visited = [[0 for i in range(w)] for j in range(h)]#visited初期化
print(ans-1)

from collections import deque
H,W = map(int,input().split())
field = [list(input()) for _ in range(H)]
dist = [[-1]*W for _ in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
mx = 0
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            continue
        dist = [[-1]*W for _ in range(H)]
        dist[h][w] = 0
        que = deque([])
        que.append([h,w])
        while que != deque([]):
            u,v = que.popleft()
            for dir in range(4):
                nu = u + dx[dir]
                nv = v + dy[dir]

                if (nu < 0) or (nu >= H) or (nv < 0) or (nv >= W):
                    continue
                if field[nu][nv] == "#":
                    continue
                if dist[nu][nv] != -1:
                    continue
            
                que.append([nu,nv])
                dist[nu][nv] = dist[u][v] + 1
            
            
        for i in range(H):
            for j in range(W):
                if mx < dist[i][j]:
                    mx = dist[i][j]
    
print(mx)

# Https://atcoder.jp/contests/abc151/tasks/abc151_d

from collections import deque

H, W = list(map(int, input().split()))
maze = [list(input()) for i in range(H)]


def bfs(sx, sy):
    result = 0
    count = [[-1] * W for i in range(H)]
    count[sx][sy] = 0
    d = deque()
    d.append((sx, sy))
    while d:
        x, y = d.popleft()
        result = count[x][y]
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            tx, ty = x + i, y + j
            if (
                not (0 <= tx < H)
                or not (0 <= ty < W)
                or maze[tx][ty] == "#"
                or count[tx][ty] != -1
            ):
                continue
            else:
                count[tx][ty] = count[x][y] + 1
                d.append((tx, ty))
    return result


ans = 0
for i in range(W):
    for j in range(H):
        if maze[j][i] == ".":
            ans = max(ans, bfs(j, i))
print(ans)


from collections import deque
import copy
H, W = list(map(int, input().split()))
maze = []
ans = 0

for i in range(H):
    maze.append(list(input()))


distancelist = []
for i in range(H):
    tmplst = [0]*W
    
    for j in range(W):
        if maze[i][j] == '#':
            tmplst[j] = -1

    distancelist.append(tmplst)

for x in range(H):
    for y in range(W):
        if maze[x][y] == '#':
            continue

        tmpdis = copy.deepcopy(distancelist)
        d = deque()
        start = [x, y]
        d.append(start)
        while d:
            h, w = d.popleft()
            now = tmpdis[h][w]
            for i, j in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                dh, dw = h+i, w+j
                if (0 <= dh < H) and (0 <= dw < W):
                    if (tmpdis[dh][dw] == 0) and [dh, dw] != start:
                        d.append([dh, dw])
                        tmpdis[dh][dw] = now + 1

            ans = max(now, ans)


print(ans)



from collections import deque
h, w = list(map(int, input().split()))
s = [input() for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
def bfs(i, j):
    cost = [[-1 for _ in range(w)] for _ in range(h)]
    que = deque()
    cost[i][j] = 0
    que.append((i, j))
    if s[i][j] == '#':
        return 0
    while que:
        ni, nj = que.popleft()
        for k in range(4):
            if 0 <= ni+dy[k] < h and 0 <= nj+dx[k] < w:
                if cost[ni+dy[k]][nj+dx[k]] != -1:
                    continue
                if s[ni+dy[k]][nj+dx[k]] == '.':
                    cost[ni+dy[k]][nj+dx[k]] = cost[ni][nj]+1
                    que.append((ni+dy[k], nj+dx[k]))

    cc = 0
    for i in range(h):
        for j in range(w):
            if cost[i][j] > cc:
                cc = cost[i][j]
    return cc

ans = 0
for i in range(h):
    for j in range(w):
        cost = bfs(i, j)
        ans = max(ans, cost)

print(ans)


from collections import deque

h,w = map(int,input().split())
maze = []

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [ [99999999]*w for _ in range(h) ]
            
            dq = deque()
            y=i
            x=j
            d=0
            dist[y][x]=0
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h) and
                        (dist[y+m[1]][x+m[0]] > d+1) and
                            (maze[y+m[1]][x+m[0]] == ".")):
                                dist[y+m[1]][x+m[0]]=d+1
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            # print(d,i,j)
print(ans)

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#つまりlist[i] < x となる i の個数
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#つまりlist[i] <= x となる i の個数
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
def maze_solve(S_1,S_2,maze_list):
    d = deque()
    d.append([S_1,S_2])
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    while d:
        v = d.popleft()
        x = v[0]
        y = v[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
    return max(list(map(lambda x: max(x), dist)))
h,w = MI()
if h==1 and w == 2:
  print(1)
elif h == 2 and w == 1:
  print(1)
else:
  ans = 0
  maze = [list(input()) for _ in range(h)]
  dist = [[-1]*w for _ in range(h)]
  start_list = []
  for i in range(h):
      for j in range(w):
          if maze[i][j] == "#":
              dist[i][j] = 0
          else:
              start_list.append([i,j])
  dist_copy = deepcopy(dist)
  for k in start_list:
      dist = deepcopy(dist_copy)
      ans = max(ans,maze_solve(k[0],k[1],maze))
  print(ans+1)

H, W = list(map(int, input().split()))
S = [0]*(H+2)
S[0] = ''.join(['#']*(W+2))
S[-1] = ''.join(['#']*(W+2))
for i in range(1,H+1):
  S[i] = '#'+input()+'#'

maxd = 0
import queue
dy = [1,0,-1,0]
dx = [0,1,0,-1]
for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]=='.':
      visited = [[False]*(W+2) for _ in range(H+2)]
      q = queue.Queue()
      visited[h][w] = True
      q.put([h,w,0])
      while not q.empty():
        a,b,c = q.get()
        #print(a,b,c)
        for i in range(4):
          y,x = a+dy[i], b+dx[i]
          if S[y][x]=='.' and visited[y][x]==False:
            q.put([y,x,c+1])
            visited[y][x]=True
      maxd = max(maxd,c)
print(maxd)


from collections import deque
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
yudlr = [-1, 1, 0, 0]
xudlr = [0, 0, -1, 1]
D = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        d = [[-1] * W for _ in range(H)]
        d[i][j] = 0
        Q = deque()
        Q.append([i, j])
        while len(Q) > 0:
            q = Q.popleft()
            y, x = q[0], q[1]
            for k in range(4):
                y1 = y + yudlr[k]
                x1 = x + xudlr[k]
                if y1 < 0 or y1 >= H or x1 < 0 or x1 >= W:
                    continue
                if S[y1][x1] == '#':
                    continue
                if d[y1][x1] != -1:
                    continue
                d[y1][x1] = d[y][x] + 1
                Q.append([y1, x1])
        Dij = max(list(map(lambda x: max(x), d)))
        D = max(D, Dij)
print(D)

h, w = map( int, input().split() )
s = []
for _ in range( h ):
    s_i = list( str( input() ) )
    s.append( s_i )

def connect( v ):
    con_v = []
    if v[ 0 ] > 0:
        if s[ v[ 0 ] - 1 ][ v[ 1 ] ] == ".":
            con_v.append( ( v[ 0 ] - 1, v[ 1 ] ) )
    if v[ 1 ] > 0:
        if s[ v[ 0 ] ][ v[ 1 ] - 1 ] == ".":
            con_v.append( ( v[ 0 ], v[ 1 ] - 1 ) )
    if v[ 0 ] < h - 1:
        if s[ v[ 0 ] + 1 ][ v[ 1 ] ] == ".":
            con_v.append( ( v[ 0 ] + 1, v[ 1 ] ) )
    if v[ 1 ] < w - 1:
        if s[ v[ 0 ] ][ v[ 1 ] + 1 ] == ".":
            con_v.append( ( v[ 0 ], v[ 1 ] + 1 ) )
    return con_v

from heapq import heappush, heappop
INF = 10 ** 10
VISITED = 1
NOT_VISITED = 0
def longest_bfs( i, j ):
    cost = [ INF for _ in range( h * w ) ]
    cost[ i * w + j ] = 0
    visit = [ NOT_VISITED for _ in range( h * w ) ]
    queue = [ ( 0, ( i, j ) ) ]
    while len( queue ) > 0:
        c, v = heappop( queue )
        visit[ v[ 0 ] * w + v[ 1 ] ] = VISITED
        for u in connect( v ):
            if visit[ u[ 0 ] * w + u[ 1 ] ] == VISITED:
                continue
            if cost[ u[ 0 ] * w + u[ 1 ] ] > cost[ v[ 0 ] * w + v[ 1 ] ] + 1:
                cost[ u[ 0 ] * w + u[ 1 ] ] = cost[ v[ 0 ] * w + v[ 1 ] ] + 1
                heappush( queue, ( cost[ u[ 0 ] * w + u[ 1 ] ], u ) )
    return cost

longest_path = 0
for i in range( h ):
    for j in range( w ):
        if s[ i ][ j ] == "#":
            continue
        path_length = longest_bfs( i, j )
        for p in path_length:
            if p < INF and p > longest_path:
                longest_path = p
print( longest_path )

h,w = map(int,input().split())
C = [list(input()) for i in range(h)]
startls = []

for i in range(h):
    for j in range(w):
        if C[i][j] == '.':
            startls.append([i,j])
            
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
ans = 0
for start in startls:
    visited = [[-1 for i in range(w)] for i in range(h)]
    visited[start[0]][start[1]] = 0
    cost = 0
    queue = [start]
    while len(queue) > 0:
        now = queue.pop(0)
        cost = visited[now[0]][now[1]]+1
        for i in range(4):
            y = now[0]+dy_dx[i][0]
            x = now[1]+dy_dx[i][1]
            if 0 <= y < h and 0 <= x < w:
                if C[y][x] != '#' and visited[y][x] == -1:
                    visited[y][x] = cost
                    queue.append([y,x])
                    ans = max(ans,cost)
print(ans)

from collections import deque
import copy
H, W = list(map(int, input().split()))
ans = 0

distancelist = []
for i in range(H):
    maze = list(input())
    tmplst = [0]*W
    for j in range(W):
        if maze[j] == '#':
            tmplst[j] = -1

    distancelist.append(tmplst)

for x in range(H):
    for y in range(W):
        if distancelist[x][y] == -1:
            continue

        tmpdis = copy.deepcopy(distancelist)
        d = deque()
        start = [x, y]
        d.append(start)
        while d:
            h, w = d.popleft()
            now = tmpdis[h][w]
            for i, j in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                dh, dw = h+i, w+j
                if (0 <= dh < H) and (0 <= dw < W):
                    if (tmpdis[dh][dw] == 0) and [dh, dw] != start:
                        d.append([dh, dw])
                        tmpdis[dh][dw] = now + 1

            ans = max(now, ans)


print(ans)



import sys
from collections import deque

input = sys.stdin.readline


def bfs(S, sh, sw, dist):
    dist[sh][sw] = 0
    queue = deque([(sh, sw)])
    while queue:
        h, w = queue.popleft()
        for i, j in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            y, x = h + i, w + j
            if S[y][x] == "#":
                continue
            if dist[y][x] == -1:
                dist[y][x] = dist[h][w] + 1
                queue.append((y, x))


def main():
    H, W = list(map(int, input().split()))
    S = [None] * (H + 2)
    S[0] = S[-1] = "#" * (W + 2)
    for i in range(1, H + 1):
        S[i] = "".join(["#", input().rstrip(), "#"])

    ans = 0
    for sh in range(1, H + 1):
        for sw in range(1, W + 1):
            if S[sh][sw] == "#":
                continue
            dist = [[-1] * (W + 2) for _ in range(H + 2)]
            bfs(S, sh, sw, dist)
            max_dist = max(list(map(max, dist)))
            ans = max(ans, max_dist)

    print(ans)


def __starting_point():
    main()

__starting_point()

from collections import deque


MAX_H = 20
MAX_W = 20


H, W = [int(x) for x in input().split()]
S = [input() for _ in range(H)]


def valid(i, j, B):
    return 0 <= i < H and 0 <= j < W and S[i][j] == '.' and not B[i][j]


def bfs(i, j):
    B = [[False] * W for _ in range(H)]
    dist = 0
    q = deque([[i, j, -1]])
    while len(q) > 0:
        p = q.popleft()
        i = p[0]
        j = p[1]
        if B[i][j]:
            continue
        d = p[2] + 1
        dist = max(dist, d)
        B[i][j] = True
        if valid(i - 1, j, B):
            q.append([i - 1, j, d])
        if valid(i + 1, j, B):
            q.append([i + 1, j, d])
        if valid(i, j - 1, B):
            q.append([i, j - 1, d])
        if valid(i, j + 1, B):
            q.append([i, j + 1, d])
    return dist


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            ans = max(ans, bfs(i, j))
print(ans)


import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return list(map(int, input().split()))
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    H,W = i_map()
    dy_dx=[[1,0],[0,1],[-1,0],[0,-1]]
    rc=[input() for i in range(H)]
    ans = 0

    for sy in range(H):
        for sx in range(W):
            if rc[sy][sx] == "#":
                continue
            dist=[[-1 for _ in range(W)] for _ in range(H)]
            dist[sy][sx] = 0
            d=deque()
            d.append([sx,sy])
            while d:
                nx, ny = d.popleft()
                for dy,dx in dy_dx:
                    y,x = ny+dy,nx+dx
                    if 0<=y<H and 0<=x<W and rc[y][x] != "#" and dist[y][x] == -1:
                        dist[y][x] = dist[ny][nx] + 1
                        d.append([x,y])
            ans = max(ans, max(list(itertools.chain.from_iterable(dist))))
    print(ans)


def __starting_point():
    main()

__starting_point()

from collections import defaultdict, deque

h, w = map(int, input().split())
tizu = [input() for _ in range(h)]
ans = 0
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for i in range(h):
    for j in range(w):
        if tizu[i][j] == "#":
            continue
        check = [[False for _ in range(w)] for _ in range(h)]
        check[i][j] = True
        queue = deque()
        queue.append([i, j])
        queue.append(0)
        while queue:
            pos = queue.popleft()
            ans_sub = queue.popleft()
            for dh, dw in directions:
                nh = pos[0] + dh
                nw = pos[1] + dw
                if nh == -1 or nh == h or nw == -1 or nw == w:
                    continue
                if tizu[nh][nw] == "#":
                    continue
                if check[nh][nw]:
                    continue
                check[nh][nw] = True
                queue.append([nh, nw])
                queue.append(ans_sub + 1)
        ans = max(ans, ans_sub)
print(ans)

import queue
def main():
    h, w = list(map(int, input().split()))
    st = [[1]*(w+2) for _ in range(h+2)]
    for i in range(h):
        s = input()
        for j in range(w):
            if s[j] == ".":
                st[i+1][j+1] = 0
    ans = 0
    for i in range(1, h+2):
        for j in range(1, w+2):
            if st[i][j] == 0:
                fs = [[float("inf")]*(w+2) for _ in range(h+2)]
                q = queue.Queue()
                fs[i][j] = 0
                q.put([i, j])
                while not q.empty():
                    y, x = q.get()
                    if st[y-1][x] == 0 and fs[y-1][x] > fs[y][x] + 1:
                        fs[y-1][x] = fs[y][x] + 1
                        q.put([y-1, x])
                    if st[y+1][x] == 0 and fs[y+1][x] > fs[y][x] + 1:
                        fs[y+1][x] = fs[y][x] + 1
                        q.put([y+1, x])
                    if st[y][x-1] == 0 and fs[y][x-1] > fs[y][x] + 1:
                        fs[y][x-1] = fs[y][x] + 1
                        q.put([y, x-1])
                    if st[y][x+1] == 0 and fs[y][x+1] > fs[y][x] + 1:
                        fs[y][x+1] = fs[y][x] + 1
                        q.put([y, x+1])
                    if ans < fs[y][x]:
                        ans = fs[y][x]
    print(ans)

def __starting_point():
    main()

__starting_point()

from collections import deque

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

ans = 0

for startx in range(w):
    for starty in range(h):
        if grid[starty][startx] == "#":
            continue

        dist = [[10000]*w for _ in range(h)]
        dist[starty][startx] = 0
        maxDist = 0

        q = deque([(startx, starty)])

        while q:
            curx, cury = q.popleft()

            adj = [(1, 0), (-1, 0), (0, 1), (0, -1)]

            for xo, yo in adj:
                x, y = curx + xo, cury + yo

                if x < 0 or x >= w or y < 0 or y >= h:
                    continue
                if grid[y][x] == "#":
                    continue

                newDist = dist[cury][curx] + 1
                if newDist < dist[y][x]:
                    dist[y][x] = newDist
                    q.append((x, y))

                    maxDist = max(maxDist, newDist)

        ans = max(ans, maxDist)

print(ans)

from collections import deque
H, W = map(int, input().split())
f = [[s=="." for s in input()] for h in range(H)]
v = [[-1 for w in range(W)] for h in range(H)]

ans = 0
dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]
for h in range(H):
  for w in range(W):
    if not f[h][w]:
      continue
    tmp = 0
    v = [[-1 for w in range(W)] for h in range(H)]
    Q = deque([(h, w)])
    v[h][w] = 0
    while Q:
      nh, nw = Q.popleft()
      for i in range(4):
        if 0<=nh+dh[i]<H and 0<=nw+dw[i]<W and f[nh+dh[i]][nw+dw[i]] and v[nh+dh[i]][nw+dw[i]] == -1:
          v[nh+dh[i]][nw+dw[i]] = v[nh][nw]+1
          tmp = v[nh+dh[i]][nw+dw[i]]
          Q.append((nh+dh[i], nw+dw[i]))
      #for a in v:
      #  print(a)
    ans = max(ans, tmp)
print(ans)

#幅優先探索
import copy
H,W=map(int,input().split())
MAZE=[0]*H
for i in range(H):
  MAZE[i]=list(str(input()))

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def solve_maze(sy,sx):
  #多次元配列はdeepcopyを使わないといけない
  MAZE1=copy.deepcopy(MAZE)
  MAZE1[sy][sx]='#'
  queue=[]
  queue.append([sy,sx])
  d=[[100000000]*W for i in range(H)]
  d[sy][sx]=0
  while len(queue)>0:
    #Qを取り出す
    Q=queue.pop(0)
    move=d[Q[0]][Q[1]]

    #4方向をループする
    for j in range(4):
      y=Q[0]+dy[j]
      x=Q[1]+dx[j]
      if 0<=y<=(H-1) and 0<=x<=(W-1) and MAZE1[y][x] == '.':
        queue.append([y,x])
        MAZE1[y][x] = '#'
        d[y][x] = move+1
  return move

d_max=0
for i in range(H):
  for j in range(W):
    if MAZE[i][j]=='.':
      d=solve_maze(i,j)
      if d>d_max:
        d_max=d
print(d_max)

H, W = list(map(int, input().split()))
maze = [input() for i in range(H)]

direction = [
    (0, 1),
    (1, 0),
    (-1, 0),
    (0, -1)
]


def bfs(sy, sx):
    reached = [[-1] * W for _ in range(H)]
    reached[sy][sx] = 0
    from collections import deque
    que = deque([[sy, sx]])
    #d_max = 0
    while que:
        iy, ix = que.popleft()
        for d in direction:
            tx, ty = ix + d[0], iy + d[1]
            if tx >= W or ty >= H or tx < 0 or ty < 0:
                continue
            if reached[ty][tx] != -1 or maze[ty][tx] == '#':
                continue
            reached[ty][tx] = reached[iy][ix] + 1
            #d_max = max(reached[ty][tx], d_max)
            que.append([ty, tx])
    d_max = 0
    for i in range(H):
        for j in range(W):
            d_max = max(d_max,reached[i][j])

    return d_max


ans = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            ans = max(ans, bfs(i, j))

# for i in range(H):
#     for j in range(i, W):
#         for k in range(H):
#             for l in range(k, W):
#                 if maze[i][j] == '#' or maze[k][l] == '#':
#                     continue
#                 else:
#                     ans = max(ans, bfs(i, j, k, l))
print(ans)


import collections

H, W = [int(n) for n in input().split()]
MAZE = []
for i in range(H):
    MAZE.append(list(input()))

def bfs(start_x, start_y):
    d = [[-1] * W for i in range(H)]

    dx_dy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    que = collections.deque([])
    que.append((start_x, start_y))

    d[start_x][start_y] = 0
    cnt = 0
    while(que):
        p = que.popleft()
        for dx, dy in dx_dy:
            nx = p[0] + dx
            ny = p[1] + dy

            if 0 <= nx < H and 0 <= ny < W and MAZE[nx][ny] != '#' and d[nx][ny] == -1:
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
            
                cnt = max(cnt, d[p[0]][p[1]] + 1)
        
    return cnt

max_count = 0
for i in range(H):
    for j in range(W):
        if MAZE[i][j] == '#':
            continue
        count = bfs(i, j)
        max_count = max(count, max_count)

print(max_count)

H,W=list(map(int,input().split()))
l=[list(input()) for i in range(H)]
l_count=[[0]*W for i in range(H)]
from collections import deque
def answer(st_X,st_Y):#X,Y座標を指定してそこからの距離を考える
   tmp_X,tmp_Y=st_X,st_Y
   que=deque([[tmp_X,tmp_Y]])
   after=set()
   while que:#スタート地点からの距離を数えながら行ったことのない場所を探索する
      tmp_X,tmp_Y=que.popleft()
      nu=l_count[tmp_Y][tmp_X]
      after.add((tmp_X,tmp_Y))
      if tmp_X>0 and l[tmp_Y][tmp_X-1]=="." and (tmp_X-1,tmp_Y) not in after and [tmp_X-1,tmp_Y] not in que:
         l_count[tmp_Y][tmp_X-1]=nu+1
         que.append([tmp_X-1,tmp_Y])
      if tmp_Y>0 and l[tmp_Y-1][tmp_X]=="." and (tmp_X,tmp_Y-1) not in after and [tmp_X,tmp_Y-1] not in que:
         l_count[tmp_Y-1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y-1])
      if tmp_X<W-1 and l[tmp_Y][tmp_X+1]=="." and (tmp_X+1,tmp_Y) not in after and [tmp_X+1,tmp_Y] not in que:
         l_count[tmp_Y][tmp_X+1]=nu+1
         que.append([tmp_X+1,tmp_Y])
      if tmp_Y<H-1 and l[tmp_Y+1][tmp_X]=="." and (tmp_X,tmp_Y+1) not in after and [tmp_X,tmp_Y+1] not in que:
         l_count[tmp_Y+1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y+1])
ans=0
for i in range(H):
   for j in range(W):
      if l[i][j]==".":
         l_count=[[0]*W for i in range(H)]
         answer(j,i)
         tmp=max(sum(l_count,[]))
         ans=max(ans,tmp)
print(ans)

H,W=map(int,input().split())
S=[list(input())for _ in range(H)]

from collections import deque
import math


def bfs(h,w,sy,sx,S):
    maze=[[10**9]*(W)for _ in range(H)]

    maze[sy-1][sx-1]=0
    que=deque([[sy-1,sx-1]])
    count=0
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<h and 0<=nextx<w:
                dist1=S[nexty][nextx]
                dist2=maze[nexty][nextx]
            else:
                continue
            if dist1!='#':
                if dist2>maze[y][x]+1:
                    maze[nexty][nextx]=maze[y][x]+1
                    count=max(count,maze[nexty][nextx])
                    que.append([nexty,nextx])
    return count

ans=0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx]=='.':
            now=bfs(H,W,sy+1,sx+1,S)
            ans=max(ans,now)

print(ans)

from collections import deque

H,W=map(int,input().split())
S=[input() for _ in range(H)]
ans=0
d=deque([])
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    d.append((i,j,0))
    visited=[[-1]*W for _ in range(H)]
    visited[i][j]=0
    while d:
      x,y,c=d.popleft()
      for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and visited[nx][ny]==-1 and S[nx][ny]=='.':
          visited[nx][ny]=c+1
          d.append((nx,ny,c+1))
    ans=max(ans,c)
print(ans)

# 深さ優先探索による迷路の最短距離計算


import sys
import copy
import queue

# 再帰上限
sys.setrecursionlimit(10 ** 6)


# 最短距離メモ
# 0#4#
# 123
# 23#のような最終結果のためのメモ
# スタートからの最短距離が格納

def answer_sheet(meiro):
    return copy.deepcopy(meiro)


# 【周りの点の取得）
# 座標が与えられると、上下左右の4点を得る。
# 境界を超えた場合はカットされる。
def get_around_point(point, h, w):
    around_points = []

    for ij in [(-1,0),(0,1),(1,0),(0,-1)]:
        i,j=ij
        new_i = point[0] + i
        new_j = point[1] + j
        if 0 <= new_i < h and 0 <= new_j < w:
            around_points.append([new_i, new_j])
    return around_points


# ある点が道かどうかを判別する
def walkable(point, meiro):
    i = point[0]
    j = point[1]
    if meiro[i][j] == ".":
        return True
    return False


# ある点が行ったことあるかどうか
def never_had_been(point, sheet):
    if sheet[point[0]][point[1]] == ".":
        return True
    else:
        return False


# キューに、ある点の周りの行ったことのない道を追加し、シートに距離を記入
def add_load_2_queue(point, h, w, meiro, sheet, que):
    around_points = get_around_point(point, h, w)
    for around_point in around_points:
        if walkable(around_point, meiro) and never_had_been(around_point, sheet):
            que.put(around_point)
            sheet[around_point[0]][around_point[1]] = sheet[point[0]][point[1]] + 1
    return sheet, que


# ポイントが与えられたとき、その周りの道をキューに追加し、シートに記入、次のキューを取り出し同様の処理を行う。キューがなくなるまで続け、シートを返す。
def step(point, h, w, meiro, sheet, que):
    sheet, que = add_load_2_queue(point, h, w, meiro, sheet, que)
    if que.empty():
        return sheet
    next_point = que.get()
    return step(next_point, h, w, meiro, sheet, que)


# シートは、行けない場所の場合は"#"が含まれているため-1に変換
def hash2minus(sheet):
    new_sheet = []
    for gyou in sheet:
        new_gyou = []
        for item in gyou:
            if item == "#":
                new_gyou.append(-1)
            else:
                new_gyou.append(item)
        new_sheet.append(new_gyou)
    return new_sheet


# -------メイン関数---------
# スタートを決めた場合の、各場所までの最短距離を表すシートを出力
# 行けない場所の場合は-1
# 入力
# start 開始座標のリスト(例：[1,2])
# h 迷路の高さ
# w 迷路の幅
# meiro 迷路の文字列リスト
def min_dis(start, h, w, meiro):
    sheet = answer_sheet(meiro)
    que = queue.Queue()
    sheet[start[0]][start[1]] = 0
    return hash2minus(step(start, h, w, meiro, sheet, que))


import numpy as np

h, w = [int(i) for i in input().split()]
meiro = []

for i in range(h):
    meiro.append(list(input()))

ans = 0
for i in range(h):
    for j in range(w):
        if meiro[i][j] == ".":
            ans = max(ans, np.max(np.array(min_dis([i,j], h, w, meiro))))

print(ans)


from collections import deque
h, w = map(int, input().split())
ma = [["#" for _ in range(w+2)] for _ in range(h+2)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        ma[i+1][j+1] = tmp[j]
ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if ma[i][j] == "#":
            continue
        elif ma[i][j] == ".":
            p = [[-1 for _ in range(w+2)] for _ in range(h+2)]
            p[i][j] = 0
            q = deque()
            q.append([i, j])
            while q:
                y, x = q.popleft()
                if ma[y+1][x] == "." and p[y+1][x] == -1:
                    p[y+1][x] = p[y][x] + 1
                    q.append([y+1, x])
                if ma[y-1][x] == "." and p[y-1][x] == -1:
                    p[y-1][x] = p[y][x] + 1
                    q.append([y-1, x])
                if ma[y][x+1] == "." and p[y][x+1] == -1:
                    p[y][x+1] = p[y][x] + 1
                    q.append([y, x+1])
                if ma[y][x-1] == "." and p[y][x-1] == -1:
                    p[y][x-1] = p[y][x] + 1
                    q.append([y, x-1])
            for l in range(h+2):
                ans = max(ans, max(p[l]))
            # ans = max(ans, max(max(p)))
print(ans)

from collections import deque
import copy
H,W=map(int,input().split())

inf=1000000000
field=[]
for i in range(H):
  row=list(input())
  for j in range(len(row)):
    if row[j]=='#':row[j]=-1
    else:row[j]=inf
  field.append(row)
ans=inf

def isIn(x,y):
  if x<0 or x>=W:return False
  if y<0 or y>=H:return False
  return True
vector=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
for i in range(H):
  for j in range(W):
    if field[i][j]==-1:continue
    l=deque([[j,i]])
    f=copy.deepcopy(field)
    f[i][j]=0
    tmp=0
    #print('--start--')
    while l:
      x,y=l.popleft()
      #print(x,y)
      #i,jを訪問
      for v in vector:
        if not isIn(x+v[1],y+v[0]):continue
        if f[y+v[0]][x+v[1]]<=tmp:continue
        f[y+v[0]][x+v[1]]=f[y][x]+1
        l.append([x+v[1],y+v[0]])
        tmp=max(f[y+v[0]][x+v[1]],tmp)
    ans=max(ans,tmp)
print(ans)

from collections import deque

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

sl = []
flag = False
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            sl.append([i, j])

q = deque()
dire = [(0, 1), (0, -1), (1, 0), (-1, 0)]
ans = 0
for sh, sw in sl:
    c = [[0]*w for _ in range(h)]
    q.append((sh, sw, 0))
    while q:
        ph, pw, k = q.pop()
        if c[ph][pw] == 0:
            ans = max(ans, k)
            c[ph][pw] = 1
            for dh, dw in dire:
                hdh, wdw = ph+dh, pw+dw
                if 0 <= hdh < h and 0 <= wdw < w and c[hdh][wdw] == 0:
                    if s[hdh][wdw] == '.':
                        q.appendleft((hdh, wdw, k+1))

print(ans)

from collections import deque
h, w = map(int, input().split())
ma = [["#" for _ in range(w+2)] for _ in range(h+2)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        ma[i+1][j+1] = tmp[j]
ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if ma[i][j] == "#":
            continue
        elif ma[i][j] == ".":
            p = [[-1 for _ in range(w+2)] for _ in range(h+2)]
            p[i][j] = 0
            q = deque()
            q.append([i, j])
            while q:
                y, x = q.popleft()
                if ma[y+1][x] == "." and p[y+1][x] == -1:
                    p[y+1][x] = p[y][x] + 1
                    q.append([y+1, x])
                if ma[y-1][x] == "." and p[y-1][x] == -1:
                    p[y-1][x] = p[y][x] + 1
                    q.append([y-1, x])
                if ma[y][x+1] == "." and p[y][x+1] == -1:
                    p[y][x+1] = p[y][x] + 1
                    q.append([y, x+1])
                if ma[y][x-1] == "." and p[y][x-1] == -1:
                    p[y][x-1] = p[y][x] + 1
                    q.append([y, x-1])
            for l in range(1, h+1):
                ans = max(ans, max(p[l]))
            # ans = max(ans, max(max(p)))
print(ans)