class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])

        def bfs(q):

            fresh_count = 0
            max_l = 0

            while q:
                row, col, l = q.popleft()
                max_l = max(max_l, l)
                directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
                for (dr, dc) in directions:
                    r = row + dr
                    c = col + dc
                    if r in range(n) and c in range(m) and grid[r][c] == 1 and (r, c) not in visited:
                        q.append((r, c, l+1))
                        visited.add((r, c))
                        fresh_count += 1

            if fresh_count == num_fresh:
                return max_l
            else:
                return -1


        # add all rotten oranges to queu
        from collections import deque
        q = deque()
        visited = set()
        num_fresh = 0

        for r in range(n):
            for c in range(m):
                if grid[r][c] == 2:
                    q.append((r, c, 0))
                    visited.add((r, c))
                if grid[r][c] == 1:
                    num_fresh += 1

        return bfs(q)