class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        N = len(grid)
        direct = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        def invalid(r, c):
            return r < 0 or c < 0 or r == N or c == N

        visit = set()

        def dfs(r, c):
            if invalid(r, c) or not grid[r][c] or (r, c) in visit:
                return
            visit.add((r, c))
            for dr, dc in direct:
                dfs(r + dr, c + dc)

        def bfs():
            res, q = 0, deque(visit)
            while q:
                for _ in range(len(q)):
                    r, c = q.popleft()
                    for dr, dc in direct:
                        curR, curC = r + dr, c + dc
                        if invalid(curR, curC) or (curR, curC) in visit:
                            continue
                        if grid[curR][curC]:
                            return res
                        q.append((curR, curC))
                        visit.add((curR, curC))
                res += 1

        for r in range(N):
            for c in range(N):
                if grid[r][c]:
                    dfs(r, c)
                    return bfs()

class Solution:
    def shortestBridge(self, grid: list[list[int]]) -> int:
        N, direct = len(grid), [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def dfs(r, c):
            if 0 <= r < N and 0 <= c < N and grid[r][c] == 1:
                grid[r][c] = 2
                q.append((r, c))
                for dr, dc in direct:
                    dfs(r + dr, c + dc)

        q = deque()
        for r in range(N):
            for c in range(N):
                if grid[r][c]:
                    dfs(r, c)
                    break
            if q: break

        res = 0
        while q:
            for _ in range(len(q)):
                r, c = q.popleft()
                for dr, dc in direct:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < N and 0 <= nc < N:
                        if grid[nr][nc] == 1:
                            return res
                        if grid[nr][nc] == 0:
                            grid[nr][nc] = 2
                            q.append((nr, nc))
            res += 1

class Solution:
    def shortestBridge(self, grid: list[list[int]]) -> int:
        N, direct = len(grid), [(0, 1), (0, -1), (1, 0), (-1, 0)]
        q2 = deque()

        found = False
        for r in range(N):
            if found: break
            for c in range(N):
                if grid[r][c] == 1:
                    q1 = deque([(r, c)])
                    grid[r][c] = 2
                    while q1:
                        x, y = q1.popleft()
                        q2.append((x, y))
                        for dx, dy in direct:
                            nx, ny = x + dx, y + dy
                            if 0 <= nx < N and 0 <= ny < N and grid[nx][ny] == 1:
                                grid[nx][ny] = 2
                                q1.append((nx, ny))
                    found = True
                    break

        res = 0
        while q2:
            for _ in range(len(q2)):
                x, y = q2.popleft()
                for dx, dy in direct:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < N and 0 <= ny < N:
                        if grid[nx][ny] == 1:
                            return res
                        if grid[nx][ny] == 0:
                            grid[nx][ny] = 2
                            q2.append((nx, ny))
            res += 1

        return res

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

    def find(self, node):
        cur = node
        while cur != self.parent[cur]:
            self.parent[cur] = self.parent[self.parent[cur]]
            cur = self.parent[cur]
        return cur

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv:
            return False
        if self.rank[pv] > self.rank[pu]:
            pu, pv = pv, pu
        self.parent[pv] = pu
        self.rank[pu] += self.rank[pv]
        return True

class Solution:
    def shortestBridge(self, grid: list[list[int]]) -> int:
        n, direct = len(grid), [(0, 1), (0, -1), (1, 0), (-1, 0)]
        dsu = DSU(n * n + 1)

        def idx(r, c):
            return r * n + c + 1

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    first_island = dsu.find(idx(r, c))
                    if c + 1 < n and grid[r][c + 1] == 1:
                        dsu.union(idx(r, c), idx(r, c + 1))
                    if r + 1 < n and grid[r + 1][c] == 1:
                        dsu.union(idx(r, c), idx(r + 1, c))

        q = deque()
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    if dsu.find(idx(r, c)) != first_island:
                        continue
                    for dx, dy in direct:
                        nr, nc = r + dx, c + dy
                        if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                            q.append((r,c))
                            break

        res = 0
        while q:
            for _ in range(len(q)):
                r, c = q.popleft()
                for dx, dy in direct:
                    nr, nc = r + dx, c + dy
                    if 0 <= nr < n and 0 <= nc < n:
                        if grid[nr][nc] == 1 and dsu.union(idx(r, c), idx(nr, nc)):
                            return res
                        if grid[nr][nc] == 0:
                            grid[nr][nc] = 1
                            dsu.union(idx(r, c), idx(nr, nc))
                            q.append((nr, nc))
            res += 1