output_description: Print the maximum possible number of moves Aoki has to make.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      H W
      S_{11}...S_{1W}
      :
      S_{H1}...S_{HW}
attempt: def two_int():
      N, K = map(int, input().split())
      return N, K
  
  
  def one_int():
      return int(input())
  
  
  def one_str():
      return input()
  
  
  def many_int():
      return list(map(int, input().split()))
  
  
  H, W = two_int()
  
  maps = [[0 for i in range(W)] for j in range(H)]
  
  for i in range(H):
      S = one_str()
      for index, j in enumerate(S):
          if j == "#":
              maps[i][index] = 1
  
  import copy
  
  
  def dfs(pos, old_pos, root):
      # 停止条件
      # 深さに限らず，任意の停止条件を書く
      x, y = pos[0], pos[1]
      pos_str = str(pos[0]) + "_" + str(pos[1])
  
      if maps[y][x] == 1:
          return 0, pos
      if pos_str in root:
          return len(root) - 1, old_pos
      root[pos_str] = 1
  
      ret1, ret2, ret3, ret4 = 0, 0, 0, 0
      if x >= 1:
          ret1, pos1 = dfs([x - 1, y], pos, copy.deepcopy(root))
  
      if x < W - 1:
          ret2, pos2 = dfs([x + 1, y], pos, copy.deepcopy(root))
  
      if y >= 1:
          ret3, pos3 = dfs([x, y - 1], pos, copy.deepcopy(root))
  
      if y < H - 1:
          ret4, pos4 = dfs([x, y + 1], pos, copy.deepcopy(root))
  
      temp = max(ret1, ret2, ret3, ret4)
      if temp == ret1:
          return ret1, pos1
      if temp == ret2:
          return ret2, pos2
      if temp == ret3:
          return ret3, pos3
      if temp == ret4:
          return ret4, pos4
  
  
  def dfs2(pos, root, goal):
      # 停止条件
      # 深さに限らず，任意の停止条件を書く
      x, y = pos[0], pos[1]
      pos_str = str(pos[0]) + "_" + str(pos[1])
  
      if pos_str in root or maps[y][x] == 1:
          return 1000
  
      if pos_str == goal_str:
          return len(root)
  
      root[pos_str] = 1
  
      ret1, ret2, ret3, ret4 = 1000, 1000, 1000, 1000
      if x >= 1:
          ret1 = dfs2([x - 1, y], copy.deepcopy(root), goal_str)
  
      if x < W - 1:
          ret2 = dfs2([x + 1, y], copy.deepcopy(root), goal_str)
  
      if y >= 1:
          ret3 = dfs2([x, y - 1], copy.deepcopy(root), goal_str)
  
      if y < H - 1:
          ret4 = dfs2([x, y + 1], copy.deepcopy(root), goal_str)
  
      return min(ret1, ret2, ret3, ret4)
  
  
  # start位置探索
  for y in range(H):
      for x in range(W):
          if maps[y][x] == 0:
              break
  
  # max(dfs([0,0],{}), dfs([0,H-1],{}), dfs([W-1,0],{}), dfs([W-1,H-1],{}))
  
  pos, goal = dfs([x, y], [0, 0], {})
  
  goal_str = str(goal[0]) + "_" + str(goal[1])
  
  print(dfs2([x, y], {}, goal_str))
  
problem_description: Statement
  
  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.
samples: [{"input": "3 3\n    ...\n    ...\n    ...", "output": "4\n    \n\nIf Takahashi chooses the top-left square as the starting square and the\nbottom-right square as the goal square, Aoki has to make four moves.\n\n* * *"}, {"input": "3 5\n    ...#.\n    .#.#.\n    .#...", "output": "10\n    \n\nIf Takahashi chooses the bottom-left square as the starting square and the\ntop-right square as the goal square, Aoki has to make ten moves."}]