1from collections import deque
2
3class Solution:
4    def shortestBridge(self, grid: List[List[int]]) -> int:
5        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
6
7        def dfs(x, y, queue):
8            if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] != 1:
9                return
10            grid[x][y] = 2
11            queue.append((x, y))
12            for dx, dy in directions:
13                dfs(x + dx, y + dy, queue)
14
15        n = len(grid)
16        found = False
17        queue = deque()
18
19        for i in range(n):
20            for j in range(n):
21                if grid[i][j] == 1:
22                    dfs(i, j, queue)
23                    found = True
24                    break
25            if found:
26                break
27
28        steps = 0
29        while queue:
30            size = len(queue)
31            for _ in range(size):
32                x, y = queue.popleft()
33                for dx, dy in directions:
34                    nx, ny = x + dx, y + dy
35                    if nx >= 0 and nx < n and ny >= 0 and ny < n:
36                        if grid[nx][ny] == 1:
37                            return steps
38                        elif grid[nx][ny] == 0:
39                            grid[nx][ny] = 2
40                            queue.append((nx, ny))
41            steps += 1
42        return -1
43
44# Example usage
45solution = Solution()
46print(solution.shortestBridge([[0,1],[1,0]]))  # Output: 1
47print(solution.shortestBridge([[0,1,0],[0,0,0],[0,0,1]]))  # Output: 2
48print(solution.shortestBridge([[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]))  # Output: 1
49