Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import numpy as np


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = np.full((H+2, W+2), -1, dtype=np.int32)
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if depth[ny][nx] == -1 and S[ny][nx] == '.':
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import numpy as np


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = np.ones((H+2, W+2), dtype=np.int32) * -1
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if depth[ny][nx] == -1 and S[ny][nx] == '.':
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1,0), (0,1)]
    visited = [[False for j in range(W+2)] for i in range(H+2)]
    q = deque()
    q.append((y, x, 0))
    max_depth = 0
    while q:
        y, x, depth = q.popleft()
        visited[y][x] = 1
        max_depth = max(max_depth, depth)
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and visited[ny][nx] == 0:
                q.append((ny, nx, depth+1))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = deque()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H+2):
        for x in range(W+2):
            if S[y][x] == '.':
                d = bfs(y, x, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def bfs(yx, H, W, S):
    dirs = (1, W+2, -1, -W-2)
    visited = [0] * ((H+2) * (W+2))
    q = deque()
    q.append((yx, 0))
    max_depth = 0
    while q:
        yx, depth = q.popleft()
        visited[yx] = 1
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and visited[nyx] == 0:
                q.append((nyx, depth+1))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = deque()
    S.append('#' * (W+2))
    for h in range(H):
        buf = input()
        S.append('#' + buf + '#')
    S.append('#' * (W+2))
    S = ''.join(S)

    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def bfs(yx, H, W, S):
    dirs = (1, W+2, -1, -W-2)
    visited = [0] * ((H+2) * (W+2))
    q = deque()
    q.append((yx, 0))
    max_depth = 0
    while q:
        yx, depth = q.popleft()
        visited[yx] = 1
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and visited[nyx] == 0:
                q.append((nyx, depth+1))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = deque()
    S.append('#' * (W+2))
    for h in range(H):
        buf = input()
        S.append('#' + buf + '#')
    S.append('#' * (W+2))
    S = ''.join(S)

    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def bfs(yx, H, W, S):
    dirs = (1, W+2, -1, -W-2)
    visited = [0] * ((H+2) * (W+2))
    q = deque()
    q.append((yx, 0))
    max_depth = 0
    while q:
        yx, depth = q.popleft()
        visited[yx] = 1
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and visited[nyx] == 0:
                q.append((nyx, depth+1))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))

    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))
    return H, W, S


def bfs(yx, H, W, S):
    dirs = (1, W+2, -1, -W-2)
    visited = [0] * ((H+2) * (W+2))
    q = deque()
    q.append((yx, 0))
    max_depth = 0
    while len(q) > 0:
        yx, depth = q.popleft()
        visited[yx] = 1
        max_depth = max(max_depth, depth)
        if max_depth == H * W:
            break
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and visited[nyx] == 0:
                q.append((nyx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))
    return H, W, S


def bfs(yx, H, W, S):
    dirs = (1, W+2, -1, -W-2)
    visited = [0] * ((H+2) * (W+2))
    q = deque()
    q.append((yx, 0))
    max_depth = 0
    while len(q) > 0:
        yx, depth = q.popleft()
        visited[yx] = 1
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and visited[nyx] == 0:
                q.append((nyx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))
    return H, W, S


def bfs(yx, H, W, S):
    dirs = [1, W+2, -1, -W-2]
    visited = [False] * ((H+2) * (W+2))
    q = deque()
    q.append((yx, 0))
    max_depth = 0
    while len(q) > 0:
        yx, depth = q.popleft()
        visited[yx] = True
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and not visited[nyx]:
                q.append((nyx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))
    return H, W, S


def bfs(yx, H, W, S):
    dirs = [1, W+2, -1, -W-2]
    visited = [False] * ((H+2) * (W+2))
    q = deque()
    q.append((yx, 0))
    max_depth = 0
    while len(q) > 0:
        yx, depth = q.popleft()
        visited[yx] = True
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and not visited[nyx]:
                q.append((nyx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))
    return H, W, S


def bfs(yx, H, W, S):
    dirs = [1, W+2, -1, -W-2]
    visited = [False] * ((H+2) * (W+2))
    q = deque()
    q.append((yx, 0))
    max_depth = 0
    while len(q) > 0:
        yx, depth = q.popleft()
        visited[yx] = True
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and not visited[nyx]:
                q.append((nyx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))
    return H, W, S


def bfs(yx, H, W, S):
    dirs = [1, W+2, -1, -W-2]
    visited = [False] * ((H+2) * (W+2))
    q = deque()
    q.appendleft((yx, 0))
    max_depth = 0
    while len(q) > 0:
        yx, depth = q.pop()
        visited[yx] = True
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and not visited[nyx]:
                q.appendleft((nyx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))
    return H, W, S


def bfs(yx, H, W, S):
    dirs = [1, W+2, -1, -W-2]
    visited = [False] * ((H+2) * (W+2))
    q = deque()
    q.appendleft((yx, 0))
    max_depth = 0
    while len(q) > 0:
        yx, depth = q.pop()
        visited[yx] = True
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and not visited[nyx]:
                q.appendleft((nyx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))
    return H, W, S


def bfs(yx, H, W, S):
    dirs = [1, W+2, -1, -W-2]
    visited = [False for i in range((H+2) * (W+2))]
    q = deque()
    q.appendleft((yx, 0))
    max_depth = 0
    while len(q) > 0:
        yx, depth = q.pop()
        visited[yx] = True
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and not visited[nyx]:
                q.appendleft((nyx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = list()
    S.append('#' * (W+2))
    for h in range(H):
        s = '#' + input() + '#'
        S.append(s)
    S.append('#' * (W+2))
    return H, W, S


def bfs(y, x, H, W, S):
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    visited = [[False for j in range(W+2)] for i in range(H+2)]
    q = deque()
    q.appendleft((y, x, 0))
    max_depth = 0
    while len(q) > 0:
        y, x, depth = q.pop()
        visited[y][x] = True
        max_depth = max(max_depth, depth)
        for dy, dx in dirs:
            ny, nx = y+dy, x+dx
            if S[ny][nx] == '.' and not visited[ny][nx]:
                q.appendleft((ny, nx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for i, j in product(range(1, H+1), range(1, W+1)):
        if S[i][j] == '.':
            d = bfs(i, j, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = list()
    S.append(['#'] * (W+2))
    for h in range(H):
        s = list('#' + input() + '#')
        S.append(s)
    S.append(['#'] * (W+2))
    return H, W, S


def bfs(y, x, H, W, S):
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    visited = [[False for j in range(W+2)] for i in range(H+2)]
    q = deque()
    q.appendleft((y, x, 0))
    max_depth = 0
    while len(q) > 0:
        y, x, depth = q.pop()
        visited[y][x] = True
        max_depth = max(max_depth, depth)
        for dy, dx in dirs:
            ny, nx = y+dy, x+dx
            if S[ny][nx] == '.' and not visited[ny][nx]:
                q.appendleft((ny, nx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for i, j in product(range(1, H+1), range(1, W+1)):
        if S[i][j] == '.':
            d = bfs(i, j, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = list()
    S.append(['#'] * (W+2))
    for h in range(H):
        s = list('#' + input() + '#')
        S.append(s)
    S.append(['#'] * (W+2))
    return H, W, S


def bfs(y, x, H, W, S):
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    visited = [[False for j in range(W+2)] for i in range(H+2)]
    q = deque()
    q.appendleft((y, x, 0))
    max_depth = 0
    while len(q) > 0:
        y, x, depth = q.pop()
        visited[y][x] = True
        max_depth = max(max_depth, depth)
        for dy, dx in dirs:
            ny, nx = y+dy, x+dx
            if S[ny][nx] == '.' and not visited[ny][nx]:
                q.appendleft((ny, nx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for i, j in product(range(1, H+1), range(1, W+1)):
        if S[i][j] == '.':
            d = bfs(i, j, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def read():
    H, W = list(map(int, input().split()))
    S = list()
    S.append(['#'] * (W+2))
    for h in range(H):
        s = list('#' + input() + '#')
        S.append(s)
    S.append(['#'] * (W+2))
    return H, W, S


def bfs(y, x, H, W, S):
    visited = [[False for j in range(W+2)] for i in range(H+2)]
    q = deque()
    q.appendleft((y, x, 0))
    max_depth = 0
    while len(q) > 0:
        y, x, depth = q.pop()
        visited[y][x] = True
        max_depth = max(max_depth, depth)
        for dy, dx in [(0,1), (1,0), (0,-1), (-1,0)]:
            ny, nx = y+dy, x+dx
            if S[ny][nx] == '.' and not visited[ny][nx]:
                q.appendleft((ny, nx, depth+1))
    return max_depth


def reset_depth(H, W, depth, S, INF=10**7):
    for i in range(H+2):
        for j in range(W+2):
            if S[i][j] == '#':
                depth[i][j] = -2
            else:
                depth[i][j] = -1


def solve(H, W, S):
    dist_max = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if S[i][j] == '.':
                d = bfs(i, j, H, W, S)
                dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def read():
    H, W = list(map(int, input().split()))
    S = list()
    S.append(['#'] * (W+2))
    for h in range(H):
        s = list('#' + input() + '#')
        S.append(s)
    S.append(['#'] * (W+2))
    return H, W, S


def bfs(y, x, H, W, S):
    visited = [[False for j in range(W+2)] for i in range(H+2)]
    q = deque()
    q.appendleft((y, x, 0))
    max_depth = 0
    while len(q) > 0:
        y, x, depth = q.pop()
        visited[y][x] = True
        max_depth = max(max_depth, depth)
        for dy, dx in [(0,1), (1,0), (0,-1), (-1,0)]:
            ny, nx = y+dy, x+dx
            if S[ny][nx] == '.' and not visited[ny][nx]:
                q.appendleft((ny, nx, depth+1))
    return max_depth


def reset_depth(H, W, depth, S, INF=10**7):
    for i in range(H+2):
        for j in range(W+2):
            if S[i][j] == '#':
                depth[i][j] = -2
            else:
                depth[i][j] = -1


def solve(H, W, S):
    dist_max = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if S[i][j] == '.':
                d = bfs(i, j, H, W, S)
                dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Fixed submission:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()