AtCoder Beginner Contest 151 - Maze Master

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: MEDIUM

Starter code:

Solutions:
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()


from collections import deque
(h, w) = map(int, input().split())
a = [input() + '#' for _ in range(h)]
b = ['#' * (w + 1)]
r = 0
for i in range(h):
	for j in range(w):
		if a[i][j] == '.':
			b[:-1] = map(list, a)
			b[i][j] = 0
			q = deque([(i, j)])
			while q:
				(i, j) = q.popleft()
				r = max(r, b[i][j])
				d = 0
				for i1 in range(i - 1, i + 2):
					for j1 in range(j - d, j + 2, 2):
						if b[i1][j1] == '.':
							b[i1][j1] = b[i][j] + 1
							q.append((i1, j1))
					d ^= 1
print(r)


(h, w) = map(int, input().split())
m = []
for i in range(h):
	m.append(list(map(lambda x: int(x == '#'), list(input()))) + [1, 1])
m += [[1 for i in range(w + 2)]] * 2
mx = 0
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for x in range(h):
	for y in range(w):
		if m[x][y]:
			continue
		s = [(x, y)]
		c = -1
		v = [[0 for i in range(w)] for i in range(h)]
		v[x][y] = 1
		while s:
			ns = []
			for i in s:
				for j in d:
					if m[i[0] + j[0]][i[1] + j[1]] or v[i[0] + j[0]][i[1] + j[1]]:
						continue
					v[i[0] + j[0]][i[1] + j[1]] = 1
					ns.append((i[0] + j[0], i[1] + j[1]))
			s = ns
			c += 1
		mx = max(mx, c)
print(mx)


from collections import deque
(h, w) = map(int, input().split())
maze = [input() for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
res = 0
for sx in range(w):
	for sy in range(h):
		if maze[sy][sx] == '.':
			d = [[-1 for _ in range(w)] for _ in range(h)]
			que = deque([[sx, sy]])
			d[sy][sx] = 0
			while que:
				(x, y) = que.popleft()
				for i in range(4):
					nx = x + dx[i]
					ny = y + dy[i]
					if 0 <= nx < w and 0 <= ny < h and (d[ny][nx] == -1) and (maze[ny][nx] == '.'):
						que.append([nx, ny])
						d[ny][nx] = d[y][x] + 1
						if res < d[ny][nx]:
							res = d[ny][nx]
print(res)


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)


(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):
	(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)


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):
	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 = queue.pop(0)
		move = d[Q[0]][Q[1]]
		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) = map(int, input().split())
s = ['#' * (w + 2)]
s += ['#' + input() + '#' for _ in range(h)]
s.append('#' * (w + 2))
h += 2
w += 2
p = [[1, 0], [0, 1], [-1, 0], [0, -1]]
st = []
cnt = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			st.append((i, j))
			cnt += 1
ans = 0
for i in range(cnt):
	n = [st[i]]
	route = {n[0]: 0}
	c = 1
	count = 1
	while c < cnt:
		n2 = []
		for i in n:
			for j in p:
				np = (i[0] + j[0], i[1] + j[1])
				if s[np[0]][np[1]] == '.' and route.get(np, -1) == -1:
					n2.append(np)
					route[np] = count
					c += 1
		n = n2
		count += 1
	ans = max(ans, count - 1)
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()


(H, W) = map(int, input().split())
S = [None] * W
S = [list(input()) for i in range(H)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def max_distance(i, j):
	not_visit = [[-1] * W for i in range(H)]
	not_visit[i][j] = 0
	stack = [(i, j)]
	while stack != []:
		(y, x) = stack.pop(0)
		for i in range(4):
			if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H and (S[y + dy[i]][x + dx[i]] != '#') and (not_visit[y + dy[i]][x + dx[i]] == -1):
				not_visit[y + dy[i]][x + dx[i]] = not_visit[y][x] + 1
				stack.append((y + dy[i], x + dx[i]))
	return not_visit[y][x]
ans = 0
for i in range(H):
	for j in range(W):
		if S[i][j] != '#':
			ans = max(ans, max_distance(i, j))
print(ans)


INF = 10 ** 9 + 7
(H, W) = map(int, input().split())
S = list()
q = list()
S.append(['#'] * (W + 2))
for i in range(H):
	S.append(['#'] + list(input()) + ['#'])
S.append(['#'] * (W + 2))
m = 0
for y in range(1, H + 1):
	for x in range(1, W + 1):
		if S[y][x] == '#':
			continue
		D = [[INF] * (W + 2) for _ in range(H + 2)]
		D[y][x] = 0
		q.clear()
		q.append([x, y])
		while len(q) > 0:
			c = list(q.pop(0))
			for (dx, dy) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
				(ny, nx) = (c[1] + dy, c[0] + dx)
				if S[ny][nx] == '.' and D[ny][nx] == INF:
					D[ny][nx] = D[c[1]][c[0]] + 1
					q.append([nx, ny])
					m = max(m, D[ny][nx])
print(m)


(H, W) = map(int, input().split())
s = [input() for _ in range(H)]
G = [['#'] * (W + 2) for _ in range(H + 2)]
for i in range(H):
	for j in range(W):
		G[i + 1][j + 1] = s[i][j]

def search(y, x):
	q = [(y, x)]
	d = [[-1] * (W + 2) for _ in range(H + 2)]
	d[y][x] = 0
	while q:
		(y1, x1) = q.pop(0)
		for (y2, x2) in ((y1 + 1, x1), (y1, x1 + 1), (y1 - 1, x1), (y1, x1 - 1)):
			if G[y2][x2] == '.' and d[y2][x2] == -1:
				d[y2][x2] = d[y1][x1] + 1
				q.append((y2, x2))
	return max((max(_) for _ in d))
ans = 0
for i in range(H):
	for j in range(W):
		if G[i + 1][j + 1] == '.':
			ans = max(search(i + 1, j + 1), ans)
print(ans)


from collections import deque
(H, W) = map(int, input().split())
M = [list(input()) for _ in range(H)]

def bfs(i, j, d):
	d_max = 0
	used = [[False for j in range(W)] for i in range(H)]
	Q = deque()
	Q.append((i, j, d))
	used[i][j] = True
	while Q:
		(i, j, d) = Q.popleft()
		for (ni, nj) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
			if ni < 0 or nj < 0 or ni >= H or (nj >= W):
				continue
			if M[ni][nj] == '.' and (not used[ni][nj]):
				d_max = max(d_max, d + 1)
				used[ni][nj] = True
				Q.append((ni, nj, d + 1))
	return d_max
ans = 0
for i in range(H):
	for j in range(W):
		if M[i][j] == '.':
			ans = max(ans, bfs(i, j, 0))
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())
maze = [list(input()) for _ in range(H)]
dxy = [[-1, 0], [0, 1], [1, 0], [0, -1]]
ans = 0
for h in range(H):
	for w in range(W):
		if maze[h][w] == '#':
			continue
		d_maze = [[-1] * W for _ in range(H)]
		d_maze[h][w] = 0
		p = deque([[h, w]])
		while p:
			(rh, rw) = p.popleft()
			for (i, j) in dxy:
				nh = rh + i
				nw = rw + j
				if 0 <= nh < H and 0 <= nw < W and (maze[nh][nw] == '.') and (d_maze[nh][nw] == -1):
					d_maze[nh][nw] = d_maze[rh][rw] + 1
					p.append([nh, nw])
		ans = max(ans, max([max(l) for l in d_maze]))
print(ans)


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

def bfs(sx, sy):
	q = collections.deque([(sx, sy)])
	checked = [[0 for _ in range(w)] for _ in range(h)]
	checked[i][j] = 1
	res = 0
	while q:
		(qx, qy) = q.popleft()
		for (dx, dy) in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
			x = qx + dx
			y = qy + dy
			if 0 <= x < h and 0 <= y < w and (s[x][y] == '.') and (checked[x][y] == 0):
				q.append((x, y))
				checked[x][y] = checked[qx][qy] + 1
				res = max(checked[x][y], res)
	return res
ans = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			ans = max(ans, bfs(i, j) - 1)
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
nextH = [0, 1, 0, -1]
nextW = [1, 0, -1, 0]

def bfs(u, S):
	S[u[0]][u[1]] = 0
	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] == '.':
				S[h][w] = S[u[0]][u[1]] + 1
				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()])
	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 bfs(loc):
	global ans
	d = [[float('inf')] * w for i in range(h)]
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]
	que = deque([])
	que.append(loc)
	d[loc[0]][loc[1]] = 0
	while que:
		p = que.popleft()
		for i in range(4):
			nx = p[0] + dx[i]
			ny = p[1] + dy[i]
			if 0 <= nx < h and 0 <= ny < w and (maze[nx][ny] == '.') and (d[nx][ny] == float('inf')):
				d[nx][ny] = d[p[0]][p[1]] + 1
				que.append([nx, ny])
				if ans < d[nx][ny]:
					ans = d[nx][ny]
	return ans
(h, w) = map(int, input().split())
maze = [list(input()) for i in range(h)]
a = 0
ans = 0
loc = []
for i in range(h):
	for j in range(w):
		if maze[i][j] != '#':
			loc = [i, j]
		else:
			continue
		a = max(a, bfs(loc))
print(a)


def MI():
	return map(int, input().split())
from collections import deque

def bfs(field, s):
	q = deque([(0, s)])
	MOVE = [(-1, 0), (0, -1), (1, 0), (0, 1)]
	dist = [[-1] * W for i in range(H)]
	(d, i, j) = (-1, -1, -1)
	while q:
		(d, (i, j)) = q.popleft()
		if dist[i][j] != -1:
			continue
		dist[i][j] = d
		for (di, dj) in MOVE:
			ni = i + di
			nj = j + dj
			if not 0 <= ni < H or not 0 <= nj < W:
				continue
			if field[ni][nj] == '#':
				continue
			if dist[ni][nj] != -1:
				continue
			q.append((d + 1, (ni, nj)))
	return (d, i, j)
(H, W) = MI()
field = [input() for _ in range(H)]
ans = 0
for i in range(H):
	for j in range(W):
		if field[i][j] == '.':
			(d, i, j) = bfs(field, (i, j))
			ans = max(ans, d)
print(ans)


(H, W) = 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()
				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())
a = ''.join((input() + '#' for _ in range(h)))
n = len(a)
b = ['#'] * w
q = deque()
r = 0
for i in range(n):
	if a[i] == '.':
		b[:-w] = a
		b[i] = 0
		q.append(i)
		while q:
			i = q.popleft()
			r = max(r, b[i])
			for j in (-1, 1, -w - 1, w + 1):
				j += i
				if b[j] == '.':
					b[j] = b[i] + 1
					q.append(j)
print(r)


from collections import deque
m = [[1, 0], [-1, 0], [0, 1], [0, -1]]
(h, w) = map(int, input().split())
l = list()
l.append('#' * (w + 2))
for i in range(h):
	j = input()
	l.append('#' + j + '#')
l.append('#' * (w + 2))

def bfs(a, b):
	s = [[-1 for j in i] for i in l]
	s[a][b] = 0
	q = deque([[a, b]])
	while len(q) > 0:
		(x, y) = q.popleft()
		for (i, j) in m:
			if l[x + i][y + j] == '.' and s[x + i][y + j] == -1:
				q.append([x + i, y + j])
				s[x + i][y + j] = s[x][y] + 1
				num = s[x + i][y + j]
	return num
ans = []
for i in range(h + 2):
	for j in range(w + 2):
		if l[i][j] == '.':
			ans.append(bfs(i, j))
print(max(ans))


from collections import deque

def bfs(start: int):
	queue = deque([start])
	dist = {start: 0}
	while queue:
		x = queue.popleft()
		for nx in (x + 1, x - 1, x + W, x - W):
			if maze[nx] == '.' and nx not in dist:
				dist[nx] = dist[x] + 1
				queue.append(nx)
	return max(dist.values())

def main():
	global W, maze
	(H, W) = map(int, input().split())
	(H, W) = (H + 2, W + 2)
	maze = '#' * W
	for _ in range(H - 2):
		maze += '#' + input().rstrip() + '#'
	maze += '#' * W
	ans = max((bfs(i) for (i, x) in enumerate(maze) if x == '.'))
	print(ans)
main()


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)


import sys

def input():
	return sys.stdin.readline().rstrip()
from collections import deque

def bfs(start):
	que = deque([start])
	D = [-1] * (h * w)
	D[start] = 0
	while que:
		x = que.popleft()
		for next_x in (x + 1, x - 1, x + w, x - w):
			if maze[next_x] == '.' and D[next_x] == -1:
				D[next_x] = D[x] + 1
				que.append(next_x)
	return max(D)

def main():
	global h, w, maze
	(h, w) = map(int, input().split())
	h += 2
	w += 2
	maze = '#' * w
	for _ in range(h - 2):
		maze += '#' + input() + '#'
	maze += '#' * w
	print(max((bfs(i) for (i, c) in enumerate(maze) if c == '.')))
main()


(h, w) = map(int, input().split())
g = [input() for _ in range(h)]
from collections import *

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


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
(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]))
print(ans)


(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]])
	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
			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))
print(ans)


import queue
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
INF = 10 ** 18
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
ans = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			continue
		d = [[INF] * w for _ in range(h)]
		d[i][j] = 0
		q = queue.Queue()
		q.put((i, j))
		while not q.empty():
			(x, y) = q.get()
			for k in range(4):
				nx = x + dx[k]
				ny = y + dy[k]
				if 0 <= nx < h and 0 <= ny < w:
					if s[nx][ny] == '.' and d[nx][ny] == INF:
						q.put((nx, ny))
						d[nx][ny] = d[x][y] + 1
						ans = max(ans, d[nx][ny])
print(ans)


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)]
S1 = copy.deepcopy(S)
ans = []
sy = 0
sx = 0
for i in range(H):
	for j in range(W):
		c = 0
		route = deque([(i, j, 0)])
		S = copy.deepcopy(S1)
		while route:
			(a, b, n) = route.popleft()
			c = n
			if 0 <= a <= H - 1 and 0 <= b <= W - 1:
				if S[a][b] == '.':
					S[a][b] = '#'
					route.append((a + 1, b, n + 1))
					route.append((a - 1, b, n + 1))
					route.append((a, b + 1, n + 1))
					route.append((a, b - 1, n + 1))
		ans.append(c - 1)
print(max(ans))


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
(h, w) = map(int, input().split())
maze = [list(input()) for i in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		if maze[i][j] == '.':
			visited = [[0 for k in range(w)] for l in range(h)]
			visited[i][j] = 1
			que = deque([])
			que.append((i, j, 0))
			while que:
				(x, y, cnt) = que.popleft()
				for (nx, ny) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
					if 0 <= nx < h and 0 <= ny < w:
						if maze[nx][ny] == '.' and visited[nx][ny] == 0:
							que.append((nx, ny, cnt + 1))
							visited[nx][ny] = 1
			ans = max(ans, cnt)
print(ans)


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

def search(y, x):
	q = [(y, x)]
	vis = [[-1] * w for _ in range(h)]
	vis[y][x] = 0
	while q:
		(cy, cx) = q.pop(0)
		for (dy, dx) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
			(ny, nx) = (cy + dy, cx + dx)
			if 0 <= ny < h and 0 <= nx < w and (g[ny][nx] == '.') and (vis[ny][nx] == -1):
				vis[ny][nx] = vis[cy][cx] + 1
				q.append((ny, nx))
	return max((max(l) for l in vis))
ans = 0
for i in range(h):
	for j in range(w):
		if g[i][j] == '.':
			ans = max(search(i, j), ans)
print(ans)


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

def search(pos):
	D = [[0] * W for _ in range(H)]
	while len(pos) > 0:
		(x, y, depth) = pos.popleft()
		D[x][y] = -1
		for i in range(4):
			nx = x + d[i][0]
			ny = y + d[i][1]
			if 0 <= nx < H and 0 <= ny < W and (MAZE[nx][ny] == '.') and (D[nx][ny] != -1):
				pos.append((nx, ny, depth + 1))
				D[nx][ny] = -1
	return depth
for i in range(H):
	for j in range(W):
		if MAZE[i][j] == '.':
			p = deque([[i, j, 0]])
			ans_l.add(search(p))
print(max(ans_l))


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
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)


(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)


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)


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)]
			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()


from collections import deque
(h, w) = map(int, input().split())
S = [input() for _ in range(h)]
ans = 0
dxy = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for y in range(h):
	for x in range(w):
		if S[y][x] == '#':
			continue
		q = deque([(x, y)])
		dist = [[0] * w for _ in range(h)]
		visited = [[0] * w for _ in range(h)]
		visited[y][x] = 1
		while q:
			(x, y) = q.popleft()
			for (dx, dy) in dxy:
				(nx, ny) = (x + dx, y + dy)
				if not 0 <= nx < w:
					continue
				if not 0 <= ny < h:
					continue
				if visited[ny][nx]:
					continue
				if S[ny][nx] == '#':
					continue
				visited[ny][nx] = 1
				dist[ny][nx] = dist[y][x] + 1
				q.append((nx, ny))
		ans = max(ans, max((max(row) for row in dist)))
print(ans)


from collections import deque
import copy
(h, w) = map(int, input().split())
ss = [list(input()) for i in range(h)]
ans = 0
for hh in range(h):
	for ww in range(w):
		dist = [[-1] * (w + 1) for i in range(h + 1)]
		c = copy.deepcopy(ss)
		xx = c[hh][ww]
		if xx == '#':
			continue
		dist[hh][ww] = 0
		dq = deque()
		dq.append((hh, ww))
		c[hh][ww] = '#'
		while dq:
			(y, x) = dq.popleft()
			for (dx, dy) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
				nx = x + dx
				ny = y + dy
				if 0 <= nx < w and 0 <= ny < h and (c[ny][nx] != '#'):
					dq.append((ny, nx))
					c[ny][nx] = '#'
					dist[ny][nx] = dist[y][x] + 1
		for i in dist:
			ans = max(ans, max(i))
print(ans)


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)


from collections import deque
(H, W) = map(int, input().split())
H += 2
W += 2
maze = '#' * W
for _ in range(H - 2):
	maze += '#' + input() + '#'
maze += '#' * W

def bfs(root):
	if maze[root] == '#':
		return -1
	dist = [-1] * (H * W)
	dist[root] = 0
	q = deque([root])
	while q:
		x = q.popleft()
		for d in [1, -1, W, -W]:
			if maze[x + d] == '.' and dist[x + d] == -1:
				q.append(x + d)
				dist[x + d] = dist[x] + 1
	return max(dist)
ans = max((bfs(i) for i in range(H * W)))
print(ans)


from collections import deque
import copy
(H, W) = map(int, input().split())
S = [list(input()) for _ in range(H)]
neig = [(1, 0), (0, 1), (-1, 0), (0, -1)]
road = []
for h in range(H):
	for w in range(W):
		if S[h][w] == '.':
			road.append((h, w))
ans = 0
for (rh, rw) in road:
	(SC, q) = (copy.deepcopy(S), deque([(rh, rw, 0)]))
	SC[rh][rw] = 0
	while len(q) > 0:
		(h, w, i) = q.popleft()
		for (nh, nw) in neig:
			if 0 <= h - nh < H and 0 <= w - nw < W and (SC[h - nh][w - nw] == '.'):
				SC[h - nh][w - nw] = i + 1
				ans = max(ans, i + 1)
				q.append([h - nh, w - nw, i + 1])
print(ans)


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

def cost(x):
	v = [[0] * w for _ in range(h)]
	v[x[1]][x[0]] = 1
	que = [x]
	ans = -1
	while que:
		newque = []
		for (X, Y) in que:
			for (x, y) in ((0, -1), (-1, 0), (0, 1), (1, 0)):
				if 0 <= X + x < w and 0 <= Y + y < h and (g[Y + y][X + x] == '.') and (v[Y + y][X + x] == 0):
					v[Y + y][X + x] = 1
					newque.append((X + x, Y + y))
		ans += 1
		que = newque
	return ans
ans = 0
for i in range(w):
	for j in range(h):
		if g[j][i] == '.':
			ans = max(ans, cost((i, j)))
print(ans)


import sys
from collections import deque
(H, W) = 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)


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

def search(n, m):
	X = [[0] * W for _ in range(H)]
	X[n][m] = 1
	ans = -1
	que = []
	que.append((n, m))
	while que:
		newque = []
		for (x, y) in que:
			for (dx, dy) in d:
				if 0 <= x + dx < H and 0 <= y + dy < W and (s[x + dx][y + dy] == '.') and (X[x + dx][y + dy] == 0):
					X[x + dx][y + dy] = 1
					newque.append((x + dx, y + dy))
		ans += 1
		que = newque
	return ans
for i in range(H):
	for j in range(W):
		if s[i][j] == '.':
			ans = max(ans, search(i, j))
print(ans)


(n, m) = map(int, input().split())
l = ['#' + input() + '#' for an in range(n)]
l = ['#' * (m + 2)] + l + ['#' * (m + 2)]
inf = 10 ** 7
from queue import Queue as qu
mo = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ret = 0
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if l[i][j] == '.':
			q = qu()
			step = [[inf for c in range(m + 2)] for x in range(n + 2)]
			step[i][j] = 0
			q.put((i, j))
			while not q.empty():
				d = q.get()
				for g in mo:
					(c, cc) = (g[0] + d[0], g[1] + d[1])
					if step[c][cc] == inf and l[c][cc] == '.':
						q.put((c, cc))
						step[c][cc] = step[d[0]][d[1]] + 1
						ret = max(ret, step[c][cc])
print(ret)


(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
ans = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
import queue
for si in range(h):
	for sj in range(w):
		if s[si][sj] == '#':
			continue
		dist = [[-1 for a in range(w)] for b in range(h)]
		q = queue.Queue()
		q.put([si, sj])
		dist[si][sj] = 0
		while not q.empty():
			(nowi, nowj) = q.get()
			for ne in range(4):
				(nexti, nextj) = (nowi + dx[ne], nowj + dy[ne])
				if nexti < 0 or nexti >= h or nextj < 0 or (nextj >= w):
					continue
				if dist[nexti][nextj] != -1 or s[nexti][nextj] == '#':
					continue
				dist[nexti][nextj] = dist[nowi][nowj] + 1
				q.put([nexti, nextj])
				ans = max(ans, dist[nexti][nextj])
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
(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)


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)
				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
			if max_depth > global_max:
				global_max = max_depth
print(global_max)


from collections import deque
from copy import deepcopy
(h, w) = map(int, input().split())
a = [list(input()) for _ in range(h)]
r = 0
for i in range(h):
	for j in range(w):
		if a[i][j] == '.':
			b = deepcopy(a)
			q = deque()
			b[i][j] = 0
			q.append((i, j))
			while q:
				(i, j) = q.popleft()
				r = max(r, b[i][j])
				for di in range(-1, 2):
					i1 = i + di
					if 0 <= i1 < h:
						for dj in range(di % 2 - 1, 2, 2):
							j1 = j + dj
							if 0 <= j1 < w and b[i1][j1] == '.':
								b[i1][j1] = b[i][j] + 1
								q.append((i1, j1))
print(r)


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


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)


(H, W) = map(int, input().split())
s = [list(input()) for _ in range(H)]
INF = 10 << 10
V = H * W
maze = [[INF] * V for _ in range(V)]
for i in range(V):
	maze[i][i] = 0
for py in range(H):
	for px in range(W):
		if s[py][px] == '#':
			continue
		target = [(px + 1, py), (px - 1, py), (px, py + 1), (px, py - 1)]
		for (x, y) in target:
			if not (0 <= x < W and 0 <= y < H):
				continue
			if s[y][x] == '#':
				continue
			maze[W * py + px][W * y + x] = 1
for k in range(V):
	for i in range(V):
		for j in range(V):
			maze[i][j] = min(maze[i][j], maze[i][k] + maze[k][j])
print(max([j for i in maze for j in i if j != INF]))


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())
l = list()
l.append('#' * (w + 2))
for i in range(h):
	l.append('#' + input() + '#')
l.append('#' * (w + 2))
p = 0
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if l[i][j] == '#':
			continue
		s = [[-1 for a in b] for b in l]
		q = deque([[i, j]])
		s[i][j] = 0
		while len(q) > 0:
			(a, b) = q.popleft()
			for (x, y) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
				if l[a + x][b + y] == '#' or s[a + x][b + y] > -1:
					continue
				q.append([a + x, b + y])
				s[a + x][b + y] = s[a][b] + 1
		r = 0
		for x in s:
			for y in x:
				r = max(y, r)
		p = max(r, p)
print(p)


import copy, collections, itertools
(H, W) = [int(_) for _ in input().split()]
S_ = [['#'] * (W + 2)] + [['#'] + list(input()) + ['#'] for _ in range(H)] + [['#'] * (W + 2)]
ans = 0
for (i, j) in itertools.product(range(1, H + 1), range(1, W + 1)):
	if S_[i][j] == '.':
		S = copy.deepcopy(S_)
		S[i][j] = '#'
		q = collections.deque([(i, j, 0)])
		while q:
			(x, y, d) = q.popleft()
			for (dx, dy) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
				if S[x + dx][y + dy] == '.':
					(X, Y) = (x + dx, y + dy)
					S[X][Y] = '#'
					q += [(X, Y, d + 1)]
		ans = max(d, ans)
print(ans)


from collections import deque
(H, W) = map(int, input().split())
Maze = [list(input()) for _ in range(H)]
ans = 0
sy = 0
while sy < H:
	sx = 0
	while sx < W:
		if Maze[sy][sx] == '.':
			M_cnt = 0
			q = deque()
			memo = [[-1] * W for _ in range(H)]
			memo[sy][sx] = 0
			q.append([sy, sx])
			while q:
				(cy, cx) = q.popleft()
				for (ny, nx) in zip((cy, cy, cy + 1, cy - 1), (cx + 1, cx - 1, cx, cx)):
					if ny >= 0 and ny < H and (nx >= 0) and (nx < W) and (Maze[ny][nx] == '.') and (memo[ny][nx] < 0):
						q.append([ny, nx])
						memo[ny][nx] = memo[cy][cx] + 1
			ans = max(ans, max([max(m) for m in memo]))
		sx += 1
	sy += 1
print(ans)


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)


from collections import deque
(h, w) = map(int, input().split())
h += 2
w += 2
s = '#' * w
for _ in range(h - 2):
	s += '#' + input() + '#'
s += '#' * w

def bfs(start):
	que = deque([start])
	INF = 10 ** 9
	dis = [INF] * (w * h)
	dis[start] = 0
	move = (1, -1, w, -w)
	while que:
		v = que.popleft()
		for i in move:
			n = v + i
			if s[n] == '#':
				continue
			dv = dis[v]
			dn = dv + 1
			if dis[n] <= dv + 1:
				continue
			dis[n] = dn
			que.append(n)
	return max((i for i in dis if i < INF))
ans = max((bfs(v) for v in range(h * w) if s[v] != '#'))
print(ans)


(H, W) = map(int, input().split())
maze = [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 maze[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 maze[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)


import queue
(h, w) = map(int, input().split())
s = '#' * (w + 2)
for _ in range(h):
	s += '#' + input() + '#'
s += '#' * (w + 2)
ans = 0
for i in range((w + 2) * (h + 2)):
	if s[i] == '#':
		continue
	dist = [10 ** 5] * (w + 2) * (h + 2)
	dist[i] = 0
	q = queue.Queue()
	q.put(i)
	while not q.empty():
		x = q.get()
		for j in (1, -1, w + 2, -w - 2):
			if s[j + x] == '#':
				continue
			if dist[j + x] > dist[x] + 1:
				dist[j + x] = dist[x] + 1
				q.put(j + x)
	for k in range((w + 2) * (h + 2)):
		if dist[k] != 10 ** 5:
			ans = max(ans, dist[k])
print(ans)


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)


(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)


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)


import queue

def bfs(sx, sy):
	dist = [[-1 for _ in range(w)] for __ in range(h)]
	dist[sx][sy] = 0
	q = queue.Queue()
	q.put([sx, sy])
	res = 0
	while not q.empty():
		(vx, vy) = q.get()
		for (dx, dy) in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
			x = vx + dx
			y = vy + dy
			if 0 <= x < h and 0 <= y < w and (S[x][y] == '.') and (dist[x][y] == -1):
				q.put([x, y])
				dist[x][y] = dist[vx][vy] + 1
				res = max(res, dist[x][y])
	return res
(h, w) = 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] == '.':
			ans = max(ans, bfs(i, j))
print(ans)


from queue import Queue
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
ans = 0
for h in range(H):
	for w in range(W):
		if S[h][w] != '.':
			continue
		q = Queue()
		seen = [[False] * W for _ in range(H)]
		q.put((h, w, 0))
		seen[h][w] = True
		while not q.empty():
			(h, w, d) = q.get()
			for (nh, nw) in [(h + 1, w), (h, w + 1), (h - 1, w), (h, w - 1)]:
				if nh < 0 or nw < 0 or nh >= H or (nw >= W):
					continue
				if not seen[nh][nw] and S[nh][nw] == '.':
					q.put((nh, nw, d + 1))
					seen[nh][nw] = True
					ans = max(d + 1, ans)
print(ans)


from collections import deque
d = [(-1, 0), (1, 0), (0, 1), (0, -1)]

def bfs(y, x, c):
	q = deque()
	q.append((y, x, c))
	ma = 0
	visit[y][x] = 1
	while q:
		(y, x, c) = q.popleft()
		ma = max(ma, c)
		for (dy, dx) in d:
			if 0 <= y + dy < h and 0 <= x + dx < w:
				if area[y + dy][x + dx] == '.' and visit[y + dy][x + dx] == 0:
					q.append((y + dy, x + dx, c + 1))
					visit[y + dy][x + dx] = 1
	return ma
(h, w) = map(int, input().split())
area = []
for i in range(h):
	area.append(list(input()))
ans = 0
for i in range(h):
	for j in range(w):
		if area[i][j] == '.':
			visit = [[0] * w for i in range(h)]
			ans = max(ans, bfs(i, j, 0))
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 deque
(H, W) = map(int, input().split())
sheet = [[0] * (W + 2) for i in range(H + 2)]
for i in range(H):
	s = input()
	for j in range(W):
		if s[j] == '.':
			sheet[i + 1][j + 1] = 1
ans = -1
for i in range(1, H + 1):
	for j in range(1, W + 1):
		m = -1
		if sheet[i][j] == 0:
			continue
		stuck = deque([(j, i, 0)])
		log = [[10 ** 5] * (W + 2) for i in range(H + 2)]
		log[i][j] = 0
		while stuck:
			(x, y, c) = stuck.popleft()
			if c > m:
				m = c
			for (dx, dy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
				if sheet[y + dy][x + dx] == 1 and log[y + dy][x + dx] > c + 1:
					log[y + dy][x + dx] = c + 1
					stuck += [(x + dx, y + dy, c + 1)]
		if ans < m:
			ans = m
print(ans)


(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
(h, w) = map(int, input().split())
s = []
for i in range(h):
	t = input()
	s.append(t)
res = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			continue
		queue = deque([[i, j]])
		visited = [[0 for ii in range(w)] for jj in range(h)]
		visited[i][j] = 1
		while queue:
			(l, m) = queue.popleft()
			for k in range(4):
				x = l + dx[k]
				y = m + dy[k]
				if x < 0 or y < 0 or x >= h or (y >= w) or (visited[x][y] != 0) or (s[x][y] == '#'):
					continue
				visited[x][y] = visited[l][m] + 1
				queue.append([x, y])
		for ii in range(h):
			for jj in range(w):
				res = max(res, visited[ii][jj])
print(res - 1)


from collections import deque
(H, W) = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
	X += [1] + [1 if a == '#' else 0 for a in input()] + [1]
X += [1] * (W + 2)
(H, W) = (H + 2, W + 2)

def BFS(i0=0):
	Q = deque([i0])
	D = [-1] * (H * W)
	D[i0] = 0
	while Q:
		x = Q.popleft()
		for y in (x + W, x - W, x + 1, x - 1):
			if X[y] == 0:
				if D[y] == -1:
					D[y] = D[x] + 1
					Q.append(y)
	return D
ma = 0
for i in range(H):
	for j in range(W):
		if X[i * W + j] == 0:
			ma = max(ma, max(BFS(i * W + j)))
print(ma)


from collections import deque
(H, W) = list(map(int, input().split()))
S = [input() for _ in range(H)]
start = [[j, i] for i in range(W) for j in range(H)]
res = 0
for pt in start:
	v = [[0] * W for _ in range(H)]
	if S[pt[0]][pt[1]] == '#':
		continue
	q = deque([pt + [0]])
	dist = 0
	while len(q) > 0:
		(h, w, cnt) = q.popleft()
		if v[h][w] == 1:
			continue
		else:
			v[h][w] = 1
		dist = max(dist, cnt)
		for (dh, dw) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
			nh = h + dh
			nw = w + dw
			if 0 > nh or nh >= H or 0 > nw or (nw >= W) or (S[nh][nw] == '#'):
				continue
			q.append([nh, nw, cnt + 1])
	res = max(res, dist)
print(res)


from itertools import count, combinations, product
(H, W) = map(int, input().split())
H += 2
W += 2
visited = [2 ** 31] * (W * H)
for i in range(1, H - 1):
	S = input()
	for (j, v) in zip(range(1, W - 1), S):
		if v == '.':
			visited[i * W + j] = 0
res = 1
D = (W, -W, 1, -1)
for i in range(W * H):
	if visited[i] == 2 ** 31:
		continue
	q = [i]
	visited[i] = i
	for dist in count():
		if not q:
			break
		nq = []
		for j in q:
			for d in D:
				if visited[j + d] < i:
					visited[j + d] = i
					nq.append(j + d)
		q = nq
	res = max(dist, res)
print(res - 1)


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
			else:
				mp[y][x] = -2
	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)
	return
if 'doTest' not in globals():
	resolve()
	return


from collections import deque
(H, W) = map(int, input().split())
S = [list(input()) for _ in range(H)]
ans = 0

def bfs(y, x, m):
	g = [[None if S[i][j] == '.' else -1 for j in range(W)] for i in range(H)]
	g[y][x] = 0
	q = deque()
	q.append((y, x))
	while q:
		(i, j) = q.popleft()
		for (di, dj) in ((0, 1), (1, 0), (-1, 0), (0, -1)):
			ni = i + di
			nj = j + dj
			if 0 <= ni < H and 0 <= nj < W and (g[ni][nj] is None):
				g[ni][nj] = g[i][j] + 1
				q.append((ni, nj))
	return max((max(r) for r in g))
for i in range(H):
	for j in range(W):
		if S[i][j] == '.':
			deq = bfs(i, j, S)
			if ans < deq:
				ans = deq
print(ans)


from collections import deque
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			continue
		q = deque([(i, j)])
		dist = [[-1] * w for _ in range(h)]
		dist[i][j] = 0
		while q:
			(x, y) = q.popleft()
			for (k, l) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
				if 0 <= x + k < h and 0 <= y + l < w and (dist[x + k][y + l] < 0) and (s[x + k][y + l] == '.'):
					dist[x + k][y + l] = dist[x][y] + 1
					ans = max(ans, dist[x + k][y + l])
					q.append((x + k, y + l))
print(ans)


import sys
import copy
import queue
sys.setrecursionlimit(10 ** 6)

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

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)

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

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())
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)


(H, W) = map(int, input().split())
grid = [None] * H
for i in range(H):
	grid[i] = input()
ans = 0
from collections import deque
for i in range(H):
	for j in range(W):
		q = deque()
		q.append([i, j, 0])
		seen = [[False for j in range(W)] for i in range(H)]
		while q:
			node = q.popleft()
			y = node[0]
			x = node[1]
			dist = node[2]
			if grid[y][x] == '#':
				continue
			if seen[y][x]:
				continue
			seen[y][x] = True
			if dist > ans:
				ans = dist
			cases = ((0, 1), (0, -1), (1, 0), (-1, 0))
			for c in cases:
				if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
					q.append([y + c[0], x + c[1], dist + 1])
print(ans)


(h, w) = map(int, input().split())
g = [[*input()] for _ in range(h)]
from collections import *
a = 0
for sx in range(h):
	for sy in range(w):
		if g[sx][sy] == '#':
			continue
		d = [[-1] * w for _ in range(h)]
		d[sx][sy] = 0
		q = deque([(sx, sy)])
		while q:
			(x, y) = q.popleft()
			t = d[x][y] + 1
			for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
				(nx, ny) = (x + dx, y + dy)
				if 0 <= nx < h and 0 <= ny < w and (g[nx][ny] == '.') and (d[nx][ny] < 0):
					d[nx][ny] = t
					q.append((nx, ny))
					a = max(a, t)
print(a)


from collections import deque
(h, w) = map(int, input().split())
S = [input() for _ in range(h)]
inf = float('inf')
ans = 0
for i in range(h):
	for j in range(w):
		if S[i][j] == '#':
			continue
		else:
			D = [[inf for _ in range(w)] for _ in range(h)]
			D[i][j] = 0
			que = deque([(i, j)])
			while que:
				(si, sj) = que.popleft()
				for (ni, nj) in [(si + 1, sj), (si - 1, sj), (si, sj + 1), (si, sj - 1)]:
					if 0 <= ni < h and 0 <= nj < w and (S[ni][nj] != '#'):
						if D[ni][nj] > D[si][sj] + 1:
							D[ni][nj] = D[si][sj] + 1
							que.append((ni, nj))
							ans = max(ans, D[si][sj] + 1)
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()


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)


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 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)


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)


(h, w) = map(int, input().split())
s = []
for i in range(h):
	ss = input()
	s.append(ss)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
ans = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			continue
		visited = [[0 for ii in range(w)] for jj in range(h)]
		st = [[i, j]]
		visited[i][j] = 1
		while st:
			(x, y) = st.pop(0)
			for k in range(4):
				p = x + dx[k]
				q = y + dy[k]
				if p < 0 or q < 0 or p >= h or (q >= w) or (s[p][q] == '#') or (visited[p][q] != 0):
					continue
				st.append([p, q])
				visited[p][q] = visited[x][y] + 1
		for a in range(h):
			for b in range(w):
				ans = max(ans, visited[a][b])
print(ans - 1)


(h, w) = map(int, input().split())
s = []
for i in range(h):
	a = input()
	s.append(a)
ans = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
for i in range(h):
	for j in range(w):
		visited = [[0 for p in range(w)] for q in range(h)]
		c = 0
		if s[i][j] == '#':
			continue
		else:
			v = [[i, j]]
			visited[i][j] = 1
			while v:
				(x, y) = v.pop(0)
				for k in range(4):
					d = x + dx[k]
					e = y + dy[k]
					if d < 0 or e < 0 or d >= h or (e >= w) or (visited[d][e] != 0) or (s[d][e] == '#'):
						continue
					visited[d][e] = visited[x][y] + 1
					v.append([d, e])
			for ii in range(h):
				for jj in range(w):
					ans = max(ans, visited[ii][jj])
print(ans - 1)


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
dxdy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			continue
		d = [[-1] * w for _ in range(h)]
		q = deque([(i, j)])
		d[i][j] = 0
		while q:
			(y, x) = q.popleft()
			for (dx, dy) in dxdy:
				if 0 <= x + dx < w and 0 <= y + dy < h and (s[y + dy][x + dx] == '.') and (d[y + dy][x + dx] == -1):
					q.append((y + dy, x + dx))
					d[y + dy][x + dx] = d[y][x] + 1
		for row in d:
			ans = max(ans, max(row))
print(ans)


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()


(h, w) = map(int, input().split())
l = []
for i in range(h):
	s = [x for x in input()]
	l.append(s)
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def bfs(x, y):
	done = [[-1 for i in range(w)] for j in range(h)]
	(ans, cnt) = (0, 0)
	que = [[x, y, cnt]]
	done[y][x] = 0
	while que:
		(nx, ny, cnt) = que.pop(0)
		for (dx, dy) in move:
			mx = nx + dx
			my = ny + dy
			if 0 <= mx < w and 0 <= my < h and (done[my][mx] == -1) and (l[my][mx] == '.'):
				done[my][mx] = cnt + 1
				que.append([mx, my, cnt + 1])
				ans = max(ans, cnt + 1)
	return ans
ans_r = 0
for i in range(w):
	for j in range(h):
		if l[j][i] == '.':
			now = bfs(i, j)
			ans_r = max(now, ans_r)
print(ans_r)


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))


(h, w) = map(int, input().split())
import sys
import queue
mok = queue.Queue()
s = [[str(c) for c in l.strip()] for l in sys.stdin]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
maxx = 0
for i in range(h):
	for j in range(w):
		d = [[-1] * w for k in range(h)]
		d[i][j] = 0
		if s[i][j] == '.':
			mok.put([i, j])
			while not mok.empty():
				[nx, ny] = mok.get()
				for k in range(4):
					if 0 <= nx + dx[k] < h and 0 <= ny + dy[k] < w and (s[nx + dx[k]][ny + dy[k]] == '.') and (d[nx + dx[k]][ny + dy[k]] == -1):
						d[nx + dx[k]][ny + dy[k]] = d[nx][ny] + 1
						if d[nx + dx[k]][ny + dy[k]] > maxx:
							maxx = d[nx + dx[k]][ny + dy[k]]
						mok.put([nx + dx[k], ny + dy[k]])
print(maxx)


(H, W) = map(int, input().split())
grid = [None] * H
for i in range(H):
	grid[i] = input()
from collections import deque
ans = 0
INF = 10 ** 9
ans = 0
for i in range(H):
	for j in range(W):
		dist = [[INF for j in range(W)] for i in range(H)]
		q = deque()
		q.append([i, j, 0])
		while q:
			node = q.popleft()
			y = node[0]
			x = node[1]
			d = node[2]
			if grid[y][x] == '#':
				continue
			if dist[y][x] <= d:
				continue
			if ans < d:
				ans = d
			dist[y][x] = d
			cases = ((0, 1), (0, -1), (1, 0), (-1, 0))
			for c in cases:
				if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
					q.append([y + c[0], x + c[1], d + 1])
print(ans)


from collections import deque
(h, w) = map(int, input().split())
s = [input() for i in range(h)]

def bfs(i0, j0):
	INF = 100
	search = deque([(i0, j0)])
	d = [[INF] * w for i in range(h)]
	d[i0][j0] = 0
	while search:
		(i, j) = search.popleft()
		for (di, dj) in ((1, 0), (0, 1), (-1, 0), (0, -1)):
			(ni, nj) = (i + di, j + dj)
			if 0 <= ni < h and 0 <= nj < w and (s[ni][nj] == '.') and (d[ni][nj] == INF):
				search.append((ni, nj))
				d[ni][nj] = d[i][j] + 1
	return d[i][j]
max_d = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			max_dij = bfs(i, j)
			max_d = max(max_d, max_dij)
print(max_d)


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 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)


from collections import deque
(H, W) = map(int, input().split())
area = ['#'] * (W + 2)
for i in range(H):
	area += ['#'] + list(input()) + ['#']
area += ['#'] * (W + 2)
H += 2
W += 2
move = [-1, 1, W, -W]
ans = 0
for i in range(H):
	for j in range(W):
		st = W * i + j
		if area[st] == '#':
			continue
		dq = deque([])
		dist = [-1] * (H * W)
		dq.append(st)
		dist[st] = 0
		while dq:
			now = dq.popleft()
			for dx in move:
				nxt = now + dx
				if dist[nxt] >= 0 or area[nxt] == '#':
					continue
				dist[nxt] = dist[now] + 1
				ans = max(ans, dist[nxt])
				dq.append(nxt)
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)


import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi

def input():
	return sys.stdin.readline()[:-1]
import string
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
MOD = int(1000000000.0) + 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
for case in range(1, t + 1):
	ans = solve()


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)


from collections import deque
from itertools import product
INF = 1001001001
dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
(H, W) = map(int, input().split())
S = [list(input()) for i in range(H)]
ans = 0
for (i, j) in product(range(H), range(W)):
	if S[i][j] == '#':
		continue
	d = [[INF] * W for i in range(H)]
	d[i][j] = 0
	q = deque([(i, j)])
	while len(q) > 0:
		(x, y) = q.popleft()
		for (dx, dy) in dr:
			(nx, ny) = (x + dx, y + dy)
			if 0 <= nx < H and 0 <= ny < W and (S[nx][ny] != '#') and (d[nx][ny] == INF):
				d[nx][ny] = d[x][y] + 1
				ans = max(d[nx][ny], ans)
				q.append((nx, ny))
print(ans)


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)]

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) = 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)


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()


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]))
		ans = max(ans, tmp)
print(ans)


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

def dfs(start):
	Dis = [[INF] * W for _ in range(H)]
	Dis[start[0]][start[1]] = 0
	q = deque([])
	q.append(start)
	r = 0
	while len(q) != 0:
		(h, w) = q.popleft()
		for d in direc:
			(hs, ws) = (h + d[0], w + d[1])
			if not (0 <= hs < H and 0 <= ws < W):
				continue
			if Gd[hs][ws] == '.' and Dis[hs][ws] == INF:
				q.append([hs, ws])
				Dis[hs][ws] = Dis[h][w] + 1
				r = max(Dis[hs][ws], r)
	return r
ans = INF
for h in range(H):
	for w in range(W):
		if Gd[h][w] == '.':
			ans = max(ans, dfs([h, w]))
print(ans)


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

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
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)


import sys
readline = sys.stdin.readline
(H, W) = map(int, readline().split())
S = [None] * H
for i in range(H):
	S[i] = readline().rstrip()
ans = 0
from collections import deque
cases = ((1, 0), (-1, 0), (0, 1), (0, -1))
for i in range(H):
	for j in range(W):
		q = deque([[i, j, 0]])
		seen = set()
		while q:
			(y, x, d) = q.popleft()
			if S[y][x] == '#':
				continue
			if (y, x) in seen:
				continue
			seen.add((y, x))
			if d > ans:
				ans = d
			for c in cases:
				if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
					q.append([y + c[0], x + c[1], d + 1])
print(ans)


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)


from collections import deque
import sys
input = sys.stdin.readline
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
ret = 0
for sy in range(H):
	for sx in range(W):
		if S[sy][sx] == '#':
			continue
		cost = [[float('inf')] * W for _ in range(H)]
		cost[sy][sx] = 0
		q = deque([(sy, sx, 0)])
		while q:
			(cy, cx, co) = q.popleft()
			for (dy, dx) in ((0, 1), (0, -1), (1, 0), (-1, 0)):
				(ny, nx) = (cy + dy, cx + dx)
				if 0 <= ny < H and 0 <= nx < W and (S[ny][nx] != '#') and (co + 1 < cost[ny][nx]):
					q.append((ny, nx, co + 1))
					cost[ny][nx] = co + 1
					ret = max(ret, co + 1)
print(ret)


(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)


from collections import deque
(h, w) = map(int, input().split())
l = [input() for _ in range(h)]
ma = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(sx, sy):
	if l[sy][sx] == '#':
		return 0
	d = [[float('inf')] * w for i in range(h)]
	que = deque([])
	que.append((sx, sy))
	d[sy][sx] = 0
	while que:
		p = que.popleft()
		for i in range(4):
			nx = p[0] + dx[i]
			ny = p[1] + dy[i]
			if 0 <= nx < w and 0 <= ny < h and (l[ny][nx] != '#') and (d[ny][nx] == float('inf')):
				que.append((nx, ny))
				d[ny][nx] = d[p[1]][p[0]] + 1
				gx = nx
				gy = ny
	return d[gy][gx]
for i in range(h):
	for k in range(w):
		ma = max(ma, bfs(k, i))
print(ma)


import heapq
(H, W) = map(int, input().split())
area = ['#'] * (W + 2)
for i in range(H):
	area += ['#'] + list(input()) + ['#']
area += ['#'] * (W + 2)
H += 2
W += 2
move = [-1, 1, W, -W]
ans = 0
for i in range(H):
	for j in range(W):
		st = W * i + j
		if area[st] == '#':
			continue
		hq = []
		dist = [-1] * (H * W)
		dist[st] = 0
		heapq.heappush(hq, (0, st))
		while hq:
			(cost, now) = heapq.heappop(hq)
			for dx in move:
				nxt = now + dx
				if dist[nxt] >= 0 or area[nxt] == '#':
					continue
				dist[nxt] = dist[now] + 1
				ans = max(ans, dist[nxt])
				heapq.heappush(hq, (dist[nxt], nxt))
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
(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)


from collections import deque

def bfs(yy, xx):
	global ans
	d = [[float('inf')] * w for i in range(h)]
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]
	q = deque([])
	q.append((yy, xx))
	d[yy][xx] = 0
	while q:
		(y, x) = q.popleft()
		for i in range(4):
			(ny, nx) = (y + dy[i], x + dx[i])
			if 0 <= ny < h and 0 <= nx < w and (s[ny][nx] == '.') and (d[ny][nx] == float('inf')):
				d[ny][nx] = d[y][x] + 1
				q.append((ny, nx))
				if ans < d[ny][nx]:
					ans = d[ny][nx]
	return ans
(h, w) = map(int, input().split())
s = [list(input()) for i in range(h)]
a = 0
ans = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			a = max(a, bfs(i, j))
print(a)


(h, w) = map(int, input().split())
a = ['*' * (w + 2)] + ['*' + input() + '*' for _ in range(h)] + ['*' * (w + 2)]
from collections import deque
ans = 0
for p in range(h):
	for q in range(w):
		d = deque()
		m = 0
		if a[p + 1][q + 1] == '.':
			d.append([p + 1, q + 1])
			c = [[10000] * w for _ in range(h)]
			c[p][q] = 1
			di = [[0, 1], [1, 0], [-1, 0], [0, -1]]
			while d:
				g = d.popleft()
				for i in di:
					x = g[0] + i[0]
					y = g[1] + i[1]
					if a[x][y] == '.':
						if c[x - 1][y - 1] == 10000:
							d.append([x, y])
							c[x - 1][y - 1] = c[g[0] - 1][g[1] - 1] + 1
			for i in range(h):
				for j in range(w):
					if c[i][j] != 10000:
						m = max(m, c[i][j])
		ans = max(ans, m)
print(ans - 1)


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.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
(h, w) = map(int, input().split())
G = [input() for i in range(h)]
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
ans = 0
for sx in range(w):
	for sy in range(h):
		if G[sy][sx] == '#':
			continue
		dist = [[-1] * w for i in range(h)]
		dist[sy][sx] = 0
		que = deque([[sy, sx]])
		while len(que):
			(y, x) = que.popleft()
			for (dx, dy) in directions:
				nx = x + dx
				ny = y + dy
				if not (0 <= nx < w and 0 <= ny < h) or G[ny][nx] == '#':
					continue
				if dist[ny][nx] != -1:
					continue
				dist[ny][nx] = dist[y][x] + 1
				que.append([ny, nx])
		ans = max(ans, max([max(d) for d in dist]))
print(ans)


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
			max_val = max(max_val, max([max(v) for v in flg]))
	print(max_val)
abc151d_maze_master()


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)


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
import copy

def BFS(sy, sx, xy_list):
	dist = [[-1] * w for i in range(h)]
	dist[sy][sx] = 0
	xy_list[sy][sx] = '#'
	dq = deque()
	dq.append((sy, sx))
	while dq:
		(y, x) = dq.popleft()
		for (dy, dx) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
			ny = y + dy
			nx = x + dx
			if 0 <= ny < h and 0 <= nx < w and (xy_list[ny][nx] != '#'):
				dq.append((ny, nx))
				xy_list[ny][nx] = '#'
				dist[ny][nx] = dist[y][x] + 1
	return dist
(h, w) = map(int, input().split())
s = [list(input()) for i in range(h)]
ans = 0
for hh in range(h):
	for ww in range(w):
		if s[hh][ww] == '#':
			continue
		xy_list = copy.deepcopy(s)
		dist = BFS(hh, ww, xy_list)
		for d in dist:
			ans = max(ans, max(d))
print(ans)


from collections import *
from itertools import *
(h, w) = map(int, input().split())
maze = [input() for _ in range(h)]
dest = [(1, 0), (-1, 0), (0, 1), (0, -1)]
score = 0
for (sx, sy) in product(range(w), range(h)):
	if maze[sy][sx] == '#':
		continue
	r = [[-1] * w for _ in range(h)]
	r[sy][sx] = 0
	queue = deque([(sx, sy)])
	while queue:
		(x, y) = queue.popleft()
		for (dx, dy) in dest:
			(nx, ny) = (x + dx, y + dy)
			if not (0 <= nx < w and 0 <= ny < h):
				continue
			if maze[ny][nx] == '#' or r[ny][nx] != -1:
				continue
			r[ny][nx] = r[y][x] + 1
			queue.append((nx, ny))
			score = max(score, r[ny][nx])
print(score)


from collections import deque
(n, m) = map(int, input().split())
maze = [['#'] + list(input()) + ['#'] for i in range(n)]
maze = [['#'] * (m + 2)] + maze + [['#'] * (m + 2)]
step = [(0, 1), (1, 0), (-1, 0), (0, -1)]
costma = 0
for i in range(1, n + 1):
	for j in range(1, m + 1):
		v = [[0] * (m + 2) for i in range(n + 2)]
		d = deque()
		d.append((i, j, 0))
		v[i][j] = 1
		while d:
			(y, x, cost) = d.popleft()
			if maze[y][x] == '.':
				for (dy, dx) in step:
					if maze[y + dy][x + dx] == '.' and v[y + dy][x + dx] == 0:
						v[y + dy][x + dx] = 1
						d.append((y + dy, x + dx, cost + 1))
						costma = max(cost + 1, costma)
print(costma)


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

def dfs(y, x):
	q = [(y, x)]
	visited = [[-1] * W for _ in range(H)]
	visited[y][x] = 0
	while q:
		(cy, cx) = q.pop(0)
		for (dy, dx) in ((1, 0), (-1, 0), (0, -1), (0, 1)):
			nx = cx + dx
			ny = cy + dy
			if 0 <= ny < H and 0 <= nx < W and (s[ny][nx] == '.') and (visited[ny][nx] == -1):
				visited[ny][nx] = visited[cy][cx] + 1
				q.append((ny, nx))
	return max((max(i) for i in visited))
ans = 0
for h in range(H):
	for w in range(W):
		if s[h][w] == '.':
			ans = max(dfs(h, w), ans)
print(ans)


import sys
from collections import deque
input = sys.stdin.readline
(h, w) = map(int, input().split())
M = [list(input().strip()) for _ in range(h)]

def bfs(x, y):
	if M[x][y] == '#':
		return 0
	q = deque()
	q.append((x, y))
	count = [[-1] * w for _ in range(h)]
	count[x][y] = 0
	while q:
		(x, y) = q.pop()
		for (i, j) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
			if 0 <= i < h and 0 <= j < w and (count[i][j] == -1) and (M[i][j] == '.'):
				count[i][j] = count[x][y] + 1
				q.appendleft((i, j))
	return max([max(c) for c in count])
ans = 0
for i in range(h):
	for j in range(w):
		ans = max(ans, bfs(i, j))
print(ans)


from collections import deque
inf = 401
(H, W) = map(int, input().split(' '))
maze = [list(input()) for i in range(H)]
ans = 0

def short_long(a, b):
	q = deque()
	q.append((a, b))
	d = [[inf for i in range(W)] for j in range(H)]
	d[a][b] = 0
	tmp = 0
	while q:
		(x, y) = q.popleft()
		for (i, j) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			(nx, ny) = (x + i, y + j)
			if 0 <= nx < H and 0 <= ny < W and (maze[nx][ny] != '#') and (d[nx][ny] == inf):
				q.append((nx, ny))
				d[nx][ny] = d[x][y] + 1
				tmp = max(d[nx][ny], tmp)
	return tmp
for i in range(H):
	for j in range(W):
		if maze[i][j] == '.':
			ans = max(ans, short_long(i, j))
print(ans)


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 i in range(h)]
ans = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
for i in range(h):
	for j in range(w):
		Q = deque()
		Q.append((i, j, 0))
		if maze[i][j] == '#':
			continue
		dp = [[-1] * w for i in range(h)]
		dp[i][j] = 0
		while Q:
			p = Q.popleft()
			ans = max(ans, p[2])
			for k in range(4):
				nx = p[0] + dx[k]
				ny = p[1] + dy[k]
				if 0 <= nx < h and 0 <= ny < w and (maze[nx][ny] == '.') and (dp[nx][ny] == -1):
					Q.append((nx, ny, p[2] + 1))
					dp[nx][ny] = p[2] + 1
print(ans)


(h, w) = map(int, input().split())
b = [[1] * (w + 2)]
for i in range(h):
	bb = [1]
	s = input()
	for j in range(w):
		if s[j] == '#':
			bb.append(1)
		else:
			bb.append(0)
	bb.append(1)
	b.append(bb)
b.append([1] * (w + 2))
ans = 0
d = [[-1, 0], [1, 0], [0, -1], [0, 1]]
for si in range(1, h + 1):
	for sj in range(1, w + 1):
		if b[si][sj]:
			continue
		visited = {(si, sj)}
		Q = [(si, sj)]
		count = -1
		while Q:
			P = []
			for (i, j) in Q:
				for (di, dj) in d:
					if b[i + di][j + dj]:
						continue
					if (i + di, j + dj) in visited:
						continue
					visited.add((i + di, j + dj))
					P.append((i + di, j + dj))
			Q = P
			count += 1
		ans = max(ans, count)
print(ans)


import queue
(H, W) = map(int, input().split())
P = [0 for i in range(H)]
for i in range(H):
	P[i] = str(input())
ans = 0
for i in range(H * W):
	s = (i // W, i % W)
	if P[s[0]][s[1]] == '#':
		continue
	st = queue.Queue()
	st.put(s)
	log = [[-1 for i in range(W)] for j in range(H)]
	log[s[0]][s[1]] = 0
	while not st.empty():
		(y, x) = st.get()
		for (z, w) in [(y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)]:
			if 0 > z or 0 > w:
				continue
			elif z >= H or w >= W:
				continue
			elif P[z][w] == '.' and log[z][w] == -1:
				st.put((z, w))
				log[z][w] = log[y][x] + 1
				ans = max(ans, log[z][w])
print(ans)


from collections import deque
(h, w) = map(int, input().split())
s = ['#' * (w + 2)] + ['#' + input() + '#' for _ in range(h)] + ['#' * (w + 2)]
ans = 0
INF = 111111
for i in range(h + 1):
	for j in range(w + 1):
		if s[i][j] == '#':
			continue
		visited = [[0] * (w + 2) for _ in range(h + 2)]
		visited[i][j] = 1
		max_s = 0
		dq = deque([(i, j, 0)])
		while dq:
			(ci, cj, step) = dq.popleft()
			if step > max_s:
				max_s = step
			step += 1
			for (di, dj) in ((ci + 1, cj), (ci, cj + 1), (ci - 1, cj), (ci, cj - 1)):
				if s[di][dj] == '#' or visited[di][dj] == 1:
					continue
				visited[di][dj] = 1
				dq.append((di, dj, step))
		ans = max(max_s, ans)
print(ans)


from collections import deque
(H, W) = [int(v) for v in input().split()]
S = ['#' + input() + '#' for _ in range(H)]
S.insert(0, '#' * (W + 2))
S.append('#' * (W + 2))
ans = 0
for y in range(1, H + 1):
	for x in range(1, W + 1):
		if S[y][x] == '#':
			continue
		queue = deque([[x, y, 0]])
		visited = [[False] * (W + 2) for _ in range(H + 2)]
		visited[y][x] = True
		while queue:
			(x, y, c) = queue.pop()
			for (ny, nx) in [[y + 1, x], [y, x + 1], [y - 1, x], [y, x - 1]]:
				if visited[ny][nx] or S[ny][nx] == '#':
					continue
				visited[ny][nx] = True
				queue.appendleft([nx, ny, c + 1])
			ans = max(ans, c)
print(ans)


(h, w) = map(int, input().split())
ls = [input() for _ in range(h)]
from collections import deque
a = 0
for i in range(h):
	for j in range(w):
		if ls[i][j] == '#':
			continue
		d = [[-1] * w for _ in range(h)]
		d[i][j] = 0
		q = deque([(i, j)])
		while q:
			(x, y) = q.popleft()
			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 ls[nx][ny] == '.' and d[nx][ny] == -1:
					d[nx][ny] = d[x][y] + 1
					q.append((nx, ny))
		a = max(a, max((max((j for j in i)) for i in d)))
print(a)


(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
from collections import deque
ans = 0
dd = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			continue
		g = [[0] * w for _ in range(h)]
		v = [[0] * w for _ in range(h)]
		g[i][j] = 1
		q = deque([(j, i)])
		while q:
			(x, y) = q.popleft()
			for (dx, dy) in dd:
				nx = x + dx
				ny = y + dy
				if not 0 <= nx < w:
					continue
				if not 0 <= ny < h:
					continue
				if g[ny][nx]:
					continue
				if s[ny][nx] == '#':
					continue
				g[ny][nx] = 1
				v[ny][nx] = v[y][x] + 1
				q.append((nx, ny))
		for ii in v:
			ans = max(ans, max(ii))
print(ans)


from collections import deque

def bfs(maze, sy, sx):
	queue = deque([[sy, sx]])
	visited = [[0] * w for _ in range(h)]
	visited[sy][sx] = 1
	mx = 0
	while queue:
		(y, x) = queue.popleft()
		for (j, k) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
			(n_y, n_x) = (y + j, x + k)
			if not (0 <= n_y < h and 0 <= n_x < w):
				continue
			if maze[n_y][n_x] == '.' and visited[n_y][n_x] == 0:
				visited[n_y][n_x] = visited[y][x] + 1
				mx = max(mx, visited[n_y][n_x])
				queue.append([n_y, n_x])
	return mx
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
ans = 0
for sy in range(h):
	for sx in range(w):
		if s[sy][sx] == '#':
			continue
		ans = max(ans, bfs(s, sy, sx) - 1)
print(ans)


from collections import deque
import sys
(H, W) = map(int, input().split())
grid = '#' * (W + 2)
for _ in range(H):
	grid += '#' + input() + '#'
grid += '#' * (W + 2)
move = [1, -1, W + 2, -W - 2]

def bfs(start):
	lst = [10 ** 9] * ((H + 2) * (W + 2))
	lst[start] = 0
	q = deque([start])
	while q:
		x = q.popleft()
		dx = lst[x]
		for d in move:
			y = x + d
			if grid[y] == '#':
				continue
			dy = dx + 1
			if dy >= lst[y]:
				continue
			lst[y] = dy
			q.append(y)
	return max((x for x in lst if x < 10 ** 9))
print(max((bfs(i) for i in range((H + 2) * (W + 2)) if grid[i] != '#')))


from collections import deque

def bfs(y, x):
	q = deque([(y, x)])
	visited[y][x] = 0
	while q:
		(cy, cx) = q.popleft()
		for (dy, dx) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			(ny, nx) = (cy + dy, cx + dx)
			if 0 <= ny < h and 0 <= nx < w and (visited[ny][nx] == -1):
				if s[ny][nx] == '#':
					continue
				visited[ny][nx] = visited[cy][cx] + 1
				q.append((ny, nx))
	res = 0
	for i in range(h):
		for j in range(w):
			if s[i][j] != '#':
				res = max(res, visited[i][j])
	return res
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			continue
		sh = i
		sw = j
		visited = [[-1] * w for _ in range(h)]
		ans = max(ans, bfs(sh, sw))
print(ans)


(n, m) = map(int, input().split())
grid = [input() for i in range(n)]
res = 0
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for a in range(n):
	for b in range(m):
		if grid[a][b] != '.':
			continue
		vis = set([(a, b)])
		q = [(a, b, 0)]
		qi = 0
		while qi < len(q):
			(i, j, c) = q[qi]
			res = max(res, c)
			qi += 1
			for (di, dj) in dirs:
				(ni, nj) = (i + di, j + dj)
				if (ni, nj) in vis or ni < 0 or ni >= n or (nj < 0) or (nj >= m) or (grid[ni][nj] != '.'):
					continue
				vis.add((ni, nj))
				q.append((ni, nj, c + 1))
print(res)


(H, W) = map(int, input().split())
S = []
for _ in range(H):
	S.append(input())
import queue, itertools
dxy = ((1, 0), (-1, 0), (0, 1), (0, -1))
ans = 0
for s in itertools.product(range(H), range(W)):
	if S[s[0]][s[1]] == '#':
		continue
	q = queue.Queue()
	dist = [[-1] * W for _ in range(H)]
	q.put(s)
	dist[s[0]][s[1]] = 0
	while not q.empty():
		(y, x) = q.get()
		for (dx, dy) in dxy:
			(nx, ny) = (x + dx, y + dy)
			if nx < 0 or ny < 0 or nx >= W or (ny >= H) or (S[ny][nx] == '#') or (dist[ny][nx] >= 0):
				continue
			dist[ny][nx] = dist[y][x] + 1
			q.put((ny, nx))
	ans = max(ans, max(map(max, dist)))
print(ans)


from collections import deque
import copy
(H, W) = map(int, input().split())
start = set()
for y in range(H):
	for (x, w) in enumerate(input()):
		if w == '.':
			start.add((x, y))
score = 0
ssize = [(-1, 0), (0, -1), (1, 0), (0, 1)]
for xy in start:
	d = deque()
	d.append(xy + (0,))
	step = 0
	can = copy.deepcopy(start)
	can.remove(xy)
	while len(d) > 0:
		now = d.popleft()
		step = now[2]
		for (xs, ys) in ssize:
			nxt = (now[0] + xs, now[1] + ys)
			if nxt in can:
				d.append(nxt + (step + 1,))
				can.remove(nxt)
	score = max(step, score)
print(score)


from collections import deque

def BFS(s):
	q = deque()
	q.append(s)
	dist = [[10 ** 10] * (W + 2) for _ in range(H + 2)]
	dist[s[0]][s[1]] = 0
	d = ((0, 1), (0, -1), (1, 0), (-1, 0))
	far = []
	while len(q) > 0:
		(i, j) = q.popleft()
		for (di, dj) in d:
			if field[i + di][j + dj] == '.' and dist[i + di][j + dj] == 10 ** 10:
				q.append([i + di, j + dj])
				dist[i + di][j + dj] = dist[i][j] + 1
		res = dist[i][j]
	return res
(H, W) = map(int, input().split())
field = ['#' * (W + 2)]
field += ['#' + input() + '#' for _ in range(H)]
field += ['#' * (W + 2)]
res = 0
for i in range(H + 2):
	for j in range(W + 2):
		if field[i][j] == '.':
			s = [i, j]
			res = max(res, BFS(s))
print(res)


from collections import deque
(h, w) = map(int, input().split())
l = [list(input()) for _ in range(h)]
ans = 0

def bfs(y, x, m):
	g = [[None if l[i][j] == '.' else -1 for j in range(w)] for i in range(h)]
	g[y][x] = 0
	q = deque()
	q.append((y, x))
	while q:
		(i, j) = q.popleft()
		for (di, dj) in ((0, 1), (1, 0), (-1, 0), (0, -1)):
			ni = i + di
			nj = j + dj
			if 0 <= ni < h and 0 <= nj < w and (g[ni][nj] is None):
				g[ni][nj] = g[i][j] + 1
				q.append((ni, nj))
	return max((max(r) for r in g))
for i in range(h):
	for j in range(w):
		if l[i][j] == '.':
			d = bfs(i, j, l)
			if ans < d:
				ans = d
print(ans)


import sys
readline = sys.stdin.readline
(H, W) = map(int, readline().split())
grid = [readline().rstrip() for i in range(H)]
ans = 0
cases = ((0, 1), (0, -1), (1, 0), (-1, 0))
from collections import deque
for i in range(H):
	for j in range(W):
		q = deque([[i, j, 0]])
		visited = [[False] * W for i in range(H)]
		while q:
			(y, x, d) = q.popleft()
			if grid[y][x] == '#':
				continue
			if visited[y][x]:
				continue
			visited[y][x] = True
			if d > ans:
				ans = d
			for c in cases:
				if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
					q.append([y + c[0], x + c[1], d + 1])
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
		while l:
			(x, y) = l.popleft()
			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)


import queue
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
(H, W) = map(int, input().split())
S = []
for h in range(H):
	S.append(input())

def bfs(s):
	dist = [[-1] * W for _ in range(H)]
	(h, w) = s
	dist[h][w] = 0
	que = queue.Queue()
	que.put(s)
	while not que.empty():
		(h, w) = que.get()
		for d in range(4):
			nh = h + dx[d]
			nw = w + dy[d]
			if nh < 0 or H <= nh or nw < 0 or (W <= nw):
				continue
			if S[nh][nw] == '#':
				continue
			if dist[nh][nw] == -1:
				dist[nh][nw] = dist[h][w] + 1
				que.put([nh, nw])
	return dist[h][w]
ans = 0
for h in range(H):
	for w in range(W):
		if S[h][w] == '.':
			ans = max(ans, bfs([h, w]))
print(ans)


from collections import deque
(H, W) = map(int, input().split())
H += 2
W += 2
s = '#' * W
for _ in range(H - 2):
	s += '#' + input() + '#'
s += '#' * W
answer = []
for i in range(W * H):
	if s[i] == '#':
		continue
	dist = [-1] * (W * H)
	q = deque([i])
	dist[i] = 0
	while len(q) > 0:
		x = q.popleft()
		for j in [-1, 1, W, -W]:
			if s[x + j] == '.' and dist[x + j] == -1:
				q.append(x + j)
				dist[x + j] = 1 + dist[x]
	answer.append(max(dist))
print(max(answer))


from collections import *
from copy import *
(n, m) = map(int, input().split())
grid = [list('#' * (m + 2))] + [list('#' + input() + '#') for i in range(n)] + [list('#' * (m + 2))]
start = []
for i in range(1, n + 1):
	for j in range(1, m + 1):
		start.append((i, j))
ans = 0
for s in start:
	G = deepcopy(grid)
	if G[s[0]][s[1]] != '#':
		G[s[0]][s[1]] = 0
	else:
		continue
	Q = deque([s])
	while Q:
		(y, x) = Q.pop()
		for (my, mx) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
			if G[y + my][x + mx] == '.':
				G[y + my][x + mx] = G[y][x] + 1
				Q.appendleft((y + my, x + mx))
	x = max((max([0] + [j for j in i if type(j) == int]) for i in G))
	if x > ans:
		ans = x
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)


(H, W) = map(int, input().split())
m = [list(input()) for _ in range(H)]
inf = 10 ** 3
V = H * W
maze = [[inf] * V for _ in range(V)]
for i in range(V):
	maze[i][i] = 0
for py in range(H):
	for px in range(W):
		if m[py][px] == '#':
			continue
		candidate = [(px + 1, py), (px - 1, py), (px, py + 1), (px, py - 1)]
		for (x, y) in candidate:
			if not (0 <= x < W and 0 <= y < H):
				continue
			if m[y][x] == '#':
				continue
			maze[W * py + px][W * y + x] = 1
for k in range(V):
	for i in range(V):
		for j in range(V):
			maze[i][j] = min(maze[i][j], maze[i][k] + maze[k][j])
print(max([j for i in maze for j in i if j != inf]))


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)


(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)


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])))


(h, w) = [int(x) for x in input().rstrip().split()]
l = [list(input()) for i in range(h)]
move = [[1, 0], [-1, 0], [0, -1], [0, 1]]

def bfs(x, y):
	stack = [[x, y]]
	done = [[False] * w for i in range(h)]
	dist = [[0] * w for i in range(h)]
	max_val = 0
	while stack:
		(nx, ny) = stack.pop(0)
		done[ny][nx] = True
		for (dx, dy) in move:
			mx = nx + dx
			my = ny + dy
			if not 0 <= mx <= w - 1 or not 0 <= my <= h - 1 or done[my][mx] == True or (l[my][mx] == '#'):
				continue
			done[my][mx] = True
			dist[my][mx] = dist[ny][nx] + 1
			max_val = max(max_val, dist[my][mx])
			stack.append([mx, my])
	return max_val
ans = 0
for i in range(w):
	for j in range(h):
		if l[j][i] != '#':
			now = bfs(i, j)
			ans = max(ans, now)
print(ans)


(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
dyx = [(1, 0), (-1, 0), (0, 1), (0, -1)]
from collections import deque
q = deque()
ans = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			continue
		q.append((i, j))
		d = [[0] * w for _ in range(h)]
		while q:
			(y, x) = q.popleft()
			for (dy, dx) in dyx:
				(ny, nx) = (y + dy, x + dx)
				if ny == i and nx == j:
					continue
				if 0 <= ny < h and 0 <= nx < w and (d[ny][nx] == 0) and (s[ny][nx] == '.'):
					d[ny][nx] = d[y][x] + 1
					q.append((ny, nx))
		for k in range(h):
			ans = max(ans, max(d[k]))
print(ans)


def bfs(source: int):
	queue = [source]
	dist = {source: 0}
	while queue:
		x = queue.pop(0)
		for nx in (x + 1, x - 1, x + W, x - W):
			if maze[nx] == '.' and nx not in dist:
				dist[nx] = dist[x] + 1
				queue.append(nx)
	return max(dist.values())

def main():
	global W, maze
	(H, W) = map(int, input().split())
	(H, W) = (H + 2, W + 2)
	maze = '#' * W
	for _ in range(H - 2):
		maze += '#' + input().rstrip() + '#'
	maze += '#' * W
	ans = max((bfs(i) for (i, c) in enumerate(maze) if c == '.'))
	print(ans)
main()


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)


from collections import deque
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
ans = []
for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			continue
		queue = deque([[i, j]])
		visited = [[-1] * W for _ in range(H)]
		visited[i][j] = 0
		while queue:
			(y, x) = queue.popleft()
			for (k, l) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
				(new_y, new_x) = (y + k, x + l)
				if new_y < 0 or new_x < 0 or new_y >= H or (new_x >= W):
					continue
				elif S[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
					visited[new_y][new_x] = visited[y][x] + 1
					queue.append([new_y, new_x])
		L = 0
		for m in range(H):
			val = max(visited[m])
			L = max(L, val)
		ans.append(L)
print(max(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

def bfs(start: int):
	queue = deque([start])
	dist = {start: 0}
	while queue:
		x = queue.popleft()
		for nx in (x + 1, x - 1, x + W, x - W):
			if maze[nx] and nx not in dist:
				dist[nx] = dist[x] + 1
				queue.append(nx)
	return max(dist.values())

def main():
	global H, W, maze
	(H, W, *S) = open(0).read().split()
	(H, W) = (int(H) + 2, int(W) + 2)
	maze = [0] * W
	for s in S:
		maze += [0] + [c == '.' for c in s] + [0]
	maze += [0] * W
	ans = max((bfs(i) for (i, x) in enumerate(maze) if x))
	print(ans)
main()


(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
road = [(i, j) for i in range(h) for j in range(w) if s[i][j] == '.']
from collections import deque
dists = set()
for r in road:
	d = deque()
	d.append(r)
	dist = {r: 0}
	while d:
		(x, y) = d.popleft()
		if s[x][y] == '#':
			continue
		for p in [(x, y + 1), (x, y - 1), (x - 1, y), (x + 1, y)]:
			if (0 <= p[0] < h and 0 <= p[1] < w) == False:
				continue
			if s[p[0]][p[1]] == '#':
				continue
			if p in dist:
				continue
			dist[p] = dist[x, y] + 1
			d.append(p)
	dist_max = max([dist[v] for v in dist])
	dists.add(dist_max)
print(max(dists))


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())
H = H + 2
W = W + 2
grid = '#' * W
for i in range(H - 2):
	grid += '#' + input() + '#'
grid += '#' * W

def bfs(start):
	INF = 10 ** 9
	dist = [INF] * (H * W)
	dist[start] = 0
	q = deque([start])
	while q:
		v = q.popleft()
		dv = dist[v]
		for move in (-1, 1, W, -W):
			w = v + move
			if grid[w] == '#':
				continue
			dw = dv + 1
			if dw >= dist[w]:
				continue
			dist[w] = dw
			q.append(w)
	return max((x for x in dist if x < INF))
answer = max((bfs(v) for v in range(H * W) if grid[v] != '#'))
print(answer)


(H, W) = list(map(int, input().split()))
MAP = [[i for i in input()] for j in range(H)]
count = sum([l.count('.') for l in MAP])

def exaustive_search(start_h, start_w):
	determined = {(start_h, start_w): 0}
	f = lambda h, w: 0 <= h < H and 0 <= w < W
	q = [(start_h, start_w)]
	q_idx = 0
	while count != q_idx:
		(h, w) = q[q_idx]
		cost = determined[h, w]
		for (dh, dw) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
			if f(h + dh, w + dw) and (h + dh, w + dw) not in determined.keys() and (MAP[h + dh][w + dw] != '#'):
				determined[h + dh, w + dw] = cost + 1
				q.append((h + dh, w + dw))
		q_idx += 1
	return max(determined.values())
print(max([exaustive_search(h, w) for h in range(H) for w in range(W) if MAP[h][w] != '#']))


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(ans)


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
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 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) = map(int, input().split())
s = [input() for _ in range(h)]

def bfs(x, y):
	q = []
	dp = {}

	def qpush(x, y, t):
		if 0 <= x < w and 0 <= y < h and (s[y][x] != '#') and ((x, y) not in dp):
			q.append((x, y))
			dp[x, y] = t
	qpush(x, y, 0)
	while len(q) > 0:
		(x, y) = q.pop(0)
		qpush(x + 1, y, dp[x, y] + 1)
		qpush(x, y - 1, dp[x, y] + 1)
		qpush(x - 1, y, dp[x, y] + 1)
		qpush(x, y + 1, dp[x, y] + 1)
	return dp.get((x, y), 0)
t = 0
for y in range(h):
	for x in range(w):
		t = max(t, bfs(x, y))
print(t)


(n, m) = map(int, input().split())
g = [input() for _ in range(n)]

def bfs(r, c):
	t = [[-1] * m for v in g]
	q = []
	t[r][c] = 0
	q += ((r, c),)
	h = 0
	dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
	while h < len(q):
		(r, c) = q[h]
		h += 1
		for d in range(4):
			(r1, c1) = (r + dirs[d][0], c + dirs[d][1])
			if 0 <= r1 < n and 0 <= c1 < m and ('.' == g[r1][c1]) and (t[r1][c1] < 0):
				t[r1][c1] = t[r][c] + 1
				q += ((r1, c1),)
	ret = -1
	for v in t:
		ret = max(ret, max(v))
	return ret
ans = 0
for i in range(n):
	for j in range(m):
		if g[i][j] == '.':
			ans = max(ans, bfs(i, j))
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)


from collections import deque
(H, W) = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0
for h in range(H):
	for w in range(W):
		if m[h][w] == '#':
			continue
		q = deque([(h, w, 0)])
		used = set()
		while q:
			(h, w, c) = q.popleft()
			if (h, w) in used:
				continue
			ans = max(ans, c)
			if 0 <= h - 1 and m[h - 1][w] == '.' and ((h - 1, w) not in used):
				q.append((h - 1, w, c + 1))
			if h + 1 < H and m[h + 1][w] == '.' and ((h + 1, w) not in used):
				q.append((h + 1, w, c + 1))
			if 0 <= w - 1 and m[h][w - 1] == '.' and ((h, w - 1) not in used):
				q.append((h, w - 1, c + 1))
			if w + 1 < W and m[h][w + 1] == '.' and ((h, w + 1) not in used):
				q.append((h, w + 1, c + 1))
			used.add((h, w))
print(ans)


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

def BFS(q):
	flg = copy.deepcopy(S)
	while q != []:
		(cx, cy, cd) = q.pop(0)
		if flg[cx][cy] == '#':
			continue
		else:
			flg[cx][cy] = '#'
		nps = [[cx + 1, cy], [cx - 1, cy], [cx, cy + 1], [cx, cy - 1]]
		for (nx, ny) in nps:
			if 0 <= nx < H and 0 <= ny < W:
				if flg[nx][ny] != '#':
					q.append([nx, ny, cd + 1])
	return cd
ans = 0
for sx in range(H):
	for sy in range(W):
		if S[sx][sy] == '#':
			continue
		else:
			ans = max(ans, BFS([[sx, sy, 0]]))
print(ans)


from collections import deque
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			continue
		visited = [[-1] * w for _ in range(h)]
		visited[i][j] = 0
		cnt = 0
		q = deque([[i, j]])
		while q:
			(x, y) = q.popleft()
			for (k, l) in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
				(nx, ny) = (k + x, l + y)
				if nx < 0 or ny < 0 or nx >= h or (ny >= w):
					continue
				if s[nx][ny] == '.' and visited[nx][ny] == -1:
					visited[nx][ny] = visited[x][y] + 1
					q.append([nx, ny])
					ans = max(ans, visited[nx][ny])
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)]
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 collections
(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
(H, W) = map(int, input().split())
s = ['#' * (W + 2)] + ['#' + input() + '#' for _ in range(H)] + ['#' * (W + 2)]
(DH, DW) = ([0, 0, 1, -1], [1, -1, 0, 0])

def bfs(start):
	que = deque([start])
	dist = [[-1 for _ in range(W + 2)] for _ in range(H + 2)]
	dist[start[0]][start[1]] = 0
	num = 0
	while que:
		label = que.pop()
		(h, w) = (label[0], label[1])
		for (dh, dw) in zip(DH, DW):
			(hh, ww) = (h + dh, w + dw)
			if s[hh][ww] == '.' and dist[hh][ww] < 0:
				que.appendleft((hh, ww))
				dist[hh][ww] = dist[h][w] + 1
				num = max(num, dist[hh][ww])
	return num
ans = 0
for h in range(1, H + 1):
	for w in range(1, W + 1):
		if s[h][w] == '.':
			ans = max(ans, bfs((h, w)))
print(ans)