In a given 2D binary array A, there are two islands.  (An island is a 4-directionally connected group of 1s not connected to any other 1s.)
Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.
Return the smallest number of 0s that must be flipped.  (It is guaranteed that the answer is at least 1.)
 
Example 1:
Input: A = [[0,1],[1,0]]
Output: 1
Example 2:
Input: A = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
Example 3:
Input: A = [[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

 
Constraints:

2 <= A.length == A[0].length <= 100
A[i][j] == 0 or A[i][j] == 1

Source: leetcode | Difficulty: MEDIUM
Tags: Matrices

Data structures

Graph traversal

Starter code: class Solution:
    def shortestBridge(self, A: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(m, n) = (len(A), len(A[0]))
		dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		queue = deque()
		boundary = set()
		found = False
		for i in range(m):
			for j in range(n):
				if A[i][j] == 1:
					A[i][j] = 2
					queue.append((i, j))
					while queue:
						(ci, cj) = queue.popleft()
						for (di, dj) in dirs:
							(ni, nj) = (ci + di, cj + dj)
							if 0 <= ni < m and 0 <= nj < n:
								if A[ni][nj] == 1:
									A[ni][nj] = 2
									queue.append((ni, nj))
								elif A[ni][nj] == 0:
									boundary.add((ci, cj))
					found = True
					break
			if found:
				break
		queue = deque(boundary)
		steps = 0
		while queue:
			for _ in range(len(queue)):
				(i, j) = queue.popleft()
				for (di, dj) in dirs:
					(ni, nj) = (i + di, j + dj)
					if 0 <= ni < m and 0 <= nj < n:
						if A[ni][nj] == 0:
							A[ni][nj] = 2
							queue.append((ni, nj))
						elif A[ni][nj] == 1:
							return steps
			steps += 1


from collections import deque

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		q = deque()
		(m, n) = (len(A), len(A[0]))

		def explore_island(r, c):
			if not 0 <= r < m or not 0 <= c < n or A[r][c] == -1:
				return
			if A[r][c] == 1:
				A[r][c] = -1
				explore_island(r + 1, c)
				explore_island(r - 1, c)
				explore_island(r, c + 1)
				explore_island(r, c - 1)
			elif A[r][c] == 0:
				q.append((r, c, 1))

		def findFirst():
			for i in range(m):
				for j in range(n):
					if A[i][j] == 1:
						explore_island(i, j)
						return
		findFirst()
		while q:
			(cur_x, cur_y, cur_t) = q.popleft()
			for (i, j) in ((cur_x + 1, cur_y), (cur_x - 1, cur_y), (cur_x, cur_y + 1), (cur_x, cur_y - 1)):
				if 0 <= i < m and 0 <= j < n:
					if A[i][j] == 0:
						A[i][j] = -1
						q.append((i, j, cur_t + 1))
					elif A[i][j] == 1:
						return cur_t


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def dfs(i, j, n, m):
			A[i][j] = 2
			queue.append((i, j))
			directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
			for (dx, dy) in directions:
				(x, y) = (i + dx, j + dy)
				if 0 <= x < n and 0 <= y < m and (A[x][y] == 1):
					dfs(x, y, n, m)
		from collections import deque
		queue = deque()
		(n, m) = (len(A), len(A[0]))
		for i in range(n):
			for j in range(m):
				if A[i][j] == 1:
					dfs(i, j, n, m)
					break
			else:
				continue
			break
		directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		step = 0
		while queue:
			size = len(queue)
			flag = False
			for i in range(size):
				point = queue.popleft()
				(x, y) = (point[0], point[1])
				for (dx, dy) in directions:
					(_x, _y) = (x + dx, y + dy)
					if _x < 0 or _x >= n or _y < 0 or (_y >= m) or (A[_x][_y] == 2):
						continue
					if A[_x][_y] == 1:
						return step
					A[_x][_y] = 2
					queue.append((_x, _y))
			step += 1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def dfs(i, j):
			A[i][j] = -1
			bfs.append((i, j))
			for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
				if 0 <= x < n and 0 <= y < n and (A[x][y] == 1):
					dfs(x, y)

		def first():
			for i in range(n):
				for j in range(n):
					if A[i][j]:
						return (i, j)
		(n, step, bfs) = (len(A), 0, [])
		dfs(*first())
		while bfs:
			new = []
			for (i, j) in bfs:
				for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
					if 0 <= x < n and 0 <= y < n:
						if A[x][y] == 1:
							return step
						elif not A[x][y]:
							A[x][y] = -1
							new.append((x, y))
			step += 1
			bfs = new


from queue import Queue

def valid(m, i, j):
	return 0 <= i < len(m) and 0 <= j < len(m[0])

def findAnIsland(m, e):
	stack = []
	for i in range(len(m)):
		for j in range(len(m[0])):
			if m[i][j] == 1 and (i, j) not in e:
				stack.append((i, j))
				break
		else:
			continue
		break
	(result, edges) = (set(), set())
	while stack:
		(ci, cj) = stack.pop()
		result.add((ci, cj))
		for (di, dj) in ((0, 1), (1, 0), (0, -1), (-1, 0)):
			(cdi, cdj) = (ci + di, cj + dj)
			if valid(m, cdi, cdj) and (cdi, cdj) not in e and ((cdi, cdj) not in result):
				if m[cdi][cdj] == 1:
					stack.append((cdi, cdj))
				else:
					edges.add((ci, cj))
	return (result, edges)

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(a, aedges) = findAnIsland(A, set())
		(b, bedges) = findAnIsland(A, a)
		min_flip = float('inf')
		q = Queue()
		for (i, j) in aedges:
			q.put((i, j, 0))
		while not q.empty():
			(ci, cj, dist) = q.get()
			for (di, dj) in ((0, 1), (1, 0), (0, -1), (-1, 0)):
				(cdi, cdj) = (ci + di, cj + dj)
				if valid(A, cdi, cdj):
					if (cdi, cdj) in bedges:
						min_flip = min(min_flip, dist)
						return min_flip
					elif A[cdi][cdj] == 0 or A[cdi][cdj] > dist + 1:
						A[cdi][cdj] = dist + 1
						q.put((cdi, cdj, dist + 1))
		return min_flip


WATER = 0
LAND = 1
ISLAND = 2
BRIDGE = 3
DIR = ((-1, 0), (1, 0), (0, -1), (0, 1))
from copy import deepcopy

class Solution:

	def shortestBridge(self, A):
		(x0, y0) = self.findFirstLand(A)
		q = deque([(x0, y0)])
		visited = set([(x0, y0)])
		self.bfs(A, q, visited, LAND)
		q = deque(visited)
		return self.bfs(A, q, visited, WATER, LAND) - 1

	def findFirstLand(self, A):
		(m, n) = (len(A), len(A[0]))
		for x in range(m):
			for y in range(n):
				if A[x][y] == LAND:
					return (x, y)

	def bfs(self, A, q, visited, target, des=-1):
		(m, n) = (len(A), len(A[0]))
		step = 0
		while q:
			for _ in range(len(q)):
				(x, y) = q.popleft()
				for (dx, dy) in DIR:
					(nx, ny) = (x + dx, y + dy)
					if 0 <= nx <= m - 1 and 0 <= ny <= n - 1 and ((nx, ny) not in visited):
						if A[nx][ny] == des:
							return step + 1
						if A[nx][ny] == target:
							q.append((nx, ny))
							visited.add((nx, ny))
			step += 1
		return step - 1


class Solution(object):

	def shortestBridge(self, A):
		(R, C) = (len(A), len(A[0]))

		def neighbors(r, c):
			for (nr, nc) in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
				if 0 <= nr < R and 0 <= nc < C:
					yield (nr, nc)

		def get_components():
			done = set()
			components = []
			for (r, row) in enumerate(A):
				for (c, val) in enumerate(row):
					if val and (r, c) not in done:
						stack = [(r, c)]
						seen = {(r, c)}
						while stack:
							node = stack.pop()
							for nei in neighbors(*node):
								if A[nei[0]][nei[1]] and nei not in seen:
									stack.append(nei)
									seen.add(nei)
						done |= seen
						components.append(seen)
			return components
		(source, target) = get_components()
		queue = collections.deque([(node, 0) for node in source])
		done = set(source)
		while queue:
			(node, d) = queue.popleft()
			if node in target:
				return d - 1
			for nei in neighbors(*node):
				if nei not in done:
					queue.append((nei, d + 1))
					done.add(nei)


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		if len(A) == 0:
			return 0
		m = len(A)
		n = len(A[0])
		queue = []
		found = False
		for i in range(m):
			if found:
				break
			for j in range(n):
				if A[i][j] == 1:
					self.dfs(i, j, A, queue)
					found = True
					break
		directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		while queue:
			(path, x, y) = queue.pop(0)
			for (dx, dy) in directions:
				if x + dx < 0 or y + dy < 0 or x + dx >= m or (y + dy >= n):
					continue
				if A[x + dx][y + dy] == 1:
					return path
				if A[x + dx][y + dy] == 0:
					A[x + dx][y + dy] = 2
					queue.append((path + 1, x + dx, y + dy))
		return -1

	def dfs(self, i, j, grid, queue):
		queue.append((0, i, j))
		grid[i][j] = 2
		stack = [(i, j)]
		directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		while stack:
			(x, y) = stack.pop()
			for (dx, dy) in directions:
				if x + dx < 0 or y + dy < 0 or x + dx >= len(grid) or (y + dy >= len(grid[0])):
					continue
				if grid[x + dx][y + dy] == 1:
					queue.append((0, x + dx, y + dy))
					stack.append((x + dx, y + dy))
					grid[x + dx][y + dy] = 2


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		r = len(A)
		c = len(A[0])
		path = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		idx = []
		for i in range(r):
			for j in range(c):
				if A[i][j] == 1:
					idx.append((i, j))
		queue = collections.deque([idx[0]])
		seen = {tuple(idx[0])}
		island = collections.deque([(idx[0][0], idx[0][1], 0)])
		while queue:
			(x, y) = queue.popleft()
			for i in path:
				a = x + i[0]
				b = y + i[1]
				if 0 <= a < r and 0 <= b < c and (A[a][b] == 1) and ((a, b) not in seen):
					queue.append((a, b))
					seen.add((a, b))
					island.append((a, b, 0))
		while island:
			(x, y, z) = island.popleft()
			for i in path:
				a = x + i[0]
				b = y + i[1]
				if 0 <= a < r and 0 <= b < c and ((a, b) not in seen):
					if A[a][b] == 0:
						island.append((a, b, z + 1))
						seen.add((a, b))
					else:
						return z


class Solution:

	def find_island(self, i, j):
		if (i >= 0 and i < self.m) and (j >= 0 and j < self.n) and (self.grid[i][j] == 1):
			self.island.append([i, j])
			self.grid[i][j] = -1
			D = [[1, 0], [-1, 0], [0, 1], [0, -1]]
			for d in D:
				self.find_island(i + d[0], j + d[1])

	def expand_island(self):
		D = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		while len(self.island) > 0:
			[i, j] = self.island.pop(0)
			for d in D:
				if i + d[0] in range(self.m) and j + d[1] in range(self.n):
					if self.grid[i + d[0]][j + d[1]] == 1:
						return self.grid[i][j] + 1
					if self.grid[i + d[0]][j + d[1]] == 0:
						self.island.append([i + d[0], j + d[1]])
						self.grid[i + d[0]][j + d[1]] = self.grid[i][j] - 1
		return self.m + self.n - 1

	def shortestBridge(self, A: List[List[int]]) -> int:
		from itertools import product
		self.grid = A
		(self.m, self.n) = (len(A), len(A[0]))
		self.island = []
		for i in range(self.n):
			for j in range(self.m):
				if len(self.island) == 0 and self.grid[i][j] == 1:
					self.find_island(i, j)
					return abs(self.expand_island())


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def dirs(V, M, N):
			res = []
			if V[0] > 0:
				res.append((V[0] - 1, V[1]))
			if V[0] < M - 1:
				res.append((V[0] + 1, V[1]))
			if V[1] > 0:
				res.append((V[0], V[1] - 1))
			if V[1] < N - 1:
				res.append((V[0], V[1] + 1))
			return res

		def bfs(grid):
			q = []
			for j in I[0]:
				level[j] = 0
				q.append(j)
				visited.add(j)
			while q:
				v = q.pop(0)
				for neighbor in dirs(v, len(grid), len(grid[0])):
					if neighbor not in visited:
						q.append(neighbor)
						visited.add(neighbor)
						if neighbor in level:
							level[neighbor] = min(level[neighbor], level[v] + 1)
						else:
							level[neighbor] = level[v] + 1
			return

		def dfs(grid, i, j, m, n, S):
			S.add((i, j))
			vis.add((i, j))
			if i < m - 1 and (i + 1, j) not in vis and (grid[i + 1][j] == 1):
				dfs(grid, i + 1, j, m, n, S)
			if i > 0 and (i - 1, j) not in vis and (grid[i - 1][j] == 1):
				dfs(grid, i - 1, j, m, n, S)
			if j < n - 1 and (i, j + 1) not in vis and (grid[i][j + 1] == 1):
				dfs(grid, i, j + 1, m, n, S)
			if j > 0 and (i, j - 1) not in vis and (grid[i][j - 1] == 1):
				dfs(grid, i, j - 1, m, n, S)
			return
		(M, N) = (len(A), len(A[0]))
		I = []
		vis = set()
		for i in range(M):
			for j in range(N):
				if (i, j) not in vis and A[i][j] == 1:
					s = set()
					dfs(A, i, j, M, N, s)
					I.append(s)
		level = {}
		visited = set()
		bfs(A)
		return min([level[j] for j in I[1]]) - 1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(m, n) = (len(A), len(A[0]))
		(r, c) = (-1, -1)
		for (i, row) in enumerate(A):
			for (j, val) in enumerate(row):
				if val == 1:
					r = i
					c = j
					break
		if r == -1 or c == -1:
			return -1
		nei = [(0, 1), (1, 0), (0, -1), (-1, 0)]

		def dfs(A, i, j, q):
			q.append((i, j, 0))
			A[i][j] = 2
			for (dx, dy) in nei:
				nx = i + dx
				ny = j + dy
				if 0 <= nx < m and 0 <= ny < n and (A[nx][ny] == 1):
					dfs(A, nx, ny, q)
			return
		q = []
		dfs(A, r, c, q)
		while q:
			(cx, cy, dis) = q.pop(0)
			for (dx, dy) in nei:
				(nx, ny) = (cx + dx, cy + dy)
				if 0 <= nx < m and 0 <= ny < n:
					if A[nx][ny] == 1:
						return dis
					if A[nx][ny] == 0:
						q.append((nx, ny, dis + 1))
						A[nx][ny] = 2
		return -1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		rows = len(A)
		cols = len(A[0])
		directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

		def edge_check(ro, co):
			r = []
			for (y, x) in directions:
				nr = ro + y
				nc = co + x
				if nr < rows and nr >= 0 and (nc < cols) and (nc >= 0) and (A[nr][nc] == 0):
					return True
			return False
		edges_1 = []
		found_1 = False
		edges_2 = []
		for row in range(rows):
			for col in range(cols):
				if A[row][col] == 1:
					A[row][col] = '#'
					q = collections.deque([])
					q.append((row, col))
					while q:
						(r, c) = q.popleft()
						if not found_1 and edge_check(r, c):
							edges_1.append((r, c))
						elif edge_check(r, c):
							edges_2.append((r, c))
						for (y, x) in directions:
							nr = r + y
							nc = c + x
							if nr < rows and nr >= 0 and (nc < cols) and (nc >= 0) and (A[nr][nc] == 1):
								q.append((nr, nc))
								A[nr][nc] = '#'
					found_1 = True
		c1 = sorted(edges_1, key=lambda x: (x[0], x[1]))
		c2 = sorted(edges_2, key=lambda x: (x[0], x[1]))
		minn = float('inf')
		for (x1, x2) in c1:
			for (y1, y2) in c2:
				minn = min(minn, abs(x1 - y1) + abs(x2 - y2) - 1)
		return minn


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def trace_island(A, start_i, start_j, second, edges):
			queue = collections.deque()
			queue.append((start_i, start_j))
			while queue:
				(i, j) = queue.popleft()
				isedge = False
				for (di, dj) in [(1, 0), (0, 1), (-1, 0), (0, -1), (0, 0)]:
					if 0 <= di + i < len(A) and 0 <= dj + j < len(A[0]) and (A[di + i][dj + j] == 1):
						if second:
							A[di + i][dj + j] = 2
						else:
							A[di + i][dj + j] = -1
						if not (di == 0 and dj == 0):
							queue.append((di + i, dj + j))
					else:
						isedge = True
				if isedge and (not second):
					edges.append((i, j))
		outedge = []
		second = False
		for i in range(len(A)):
			for j in range(len(A[0])):
				if A[i][j] == 1:
					trace_island(A, i, j, second, outedge)
					second = True
		output = 0
		while outedge:
			temp = []
			for (i, j) in outedge:
				for (di, dj) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
					if 0 <= di + i < len(A) and 0 <= dj + j < len(A[0]) and (A[di + i][dj + j] != -1):
						if A[di + i][dj + j] == 2:
							return output
						temp.append((di + i, dj + j))
						A[di + i][dj + j] = -1
			outedge = temp
			output += 1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		q = []
		r = len(A)
		c = len(A[0])
		result = float('inf')
		seen = [[False] * c for _ in range(r)]
		found = False
		for i in range(r):
			if found:
				break
			for j in range(c):
				if A[i][j] == 1:
					q = self.neighbors(i, j, A, seen, r, c)
					found = True
					break
		while q:
			(x, y, dis) = q.pop(0)
			for (d1, d2) in ((-1, 0), (0, -1), (1, 0), (0, 1)):
				(n_x, n_y) = (d1 + x, d2 + y)
				if 0 <= n_x < r and 0 <= n_y < c and (not seen[n_x][n_y]):
					if A[n_x][n_y] == 1:
						result = min(result, dis)
					q.append((n_x, n_y, dis + 1))
					seen[n_x][n_y] = True
		return result

	def neighbors(self, i, j, A, seen, r, c):
		q = [(i, j)]
		seen[i][j] = True
		ls = []
		while q:
			(x, y) = q.pop(0)
			ls.append((x, y, 0))
			for (d1, d2) in ((-1, 0), (0, -1), (1, 0), (0, 1)):
				(n_x, n_y) = (d1 + x, d2 + y)
				if 0 <= n_x < r and 0 <= n_y < c and (A[n_x][n_y] == 1) and (not seen[n_x][n_y]):
					q.append((n_x, n_y))
					seen[n_x][n_y] = True
		return ls


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		if not len(A) or not len(A[0]):
			return 0
		(m, n) = (len(A), len(A[0]))

		def neighbors(i, j):
			for (ni, nj) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
				if 0 <= ni < m and 0 <= nj < n:
					yield (ni, nj)

		def dfs(i, j, seen, island):
			if (i, j) not in seen:
				seen.add((i, j))
				for (ni, nj) in neighbors(i, j):
					if A[ni][nj] == 1:
						dfs(ni, nj, seen, island)
					else:
						island.add((i, j))

		def find_island():
			seen = set()
			island = set()
			for i in range(m):
				for j in range(n):
					if A[i][j] == 1:
						dfs(i, j, seen, island)
						return (seen, island)
		(seen, island) = find_island()
		q = collections.deque(list([(x, 0) for x in island]))
		while q:
			((i, j), cnt) = q.popleft()
			for (ni, nj) in neighbors(i, j):
				if (ni, nj) not in seen:
					seen.add((ni, nj))
					if A[ni][nj] == 1:
						return cnt
					q.append(((ni, nj), cnt + 1))
		return -1


import queue

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def adjacent(i, q):
			nonlocal A
			l = []
			if i > 0:
				l.append([i - 1, q])
			if i < len(A) - 1:
				l.append([i + 1, q])
			if q > 0:
				l.append([i, q - 1])
			if q < len(A[0]) - 1:
				l.append([i, q + 1])
			return l

		def fill(i, q):
			nonlocal A
			A[i][q] = 2
			qu = queue.Queue()
			qu.put([i, q])
			seen = set()
			while not qu.empty():
				current = qu.get()
				seen.add(tuple(current))
				l = adjacent(current[0], current[1])
				for (a, b) in l:
					if A[a][b] == 1:
						A[a][b] = 2
						qu.put([a, b])
			return seen
		starts = []
		broken = False
		for i in range(len(A)):
			for q in range(len(A[0])):
				if A[i][q] == 1:
					starts = fill(i, q)
					broken = True
					break
			if broken:
				break
		qu = queue.Queue()
		for el in list(starts):
			qu.put(list(el) + [0])
		while not qu.empty():
			current = qu.get()
			l = adjacent(current[0], current[1])
			for (i, q) in l:
				if A[i][q] == 1:
					return current[2]
				elif A[i][q] == 0:
					A[i][q] = 2
					qu.put([i, q, current[2] + 1])


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(R, C) = (len(A), len(A[0]))
		directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

		def dfs(row, col, group):
			A[row][col] = marker
			group.append((row, col))
			for (dr, dc) in directions:
				(new_row, new_col) = (row + dr, col + dc)
				if 0 <= new_row < R and 0 <= new_col < C and (A[new_row][new_col] == 1):
					dfs(new_row, new_col, group)
			return group
		(groups, marker) = ([], 2)
		for r in range(R):
			for c in range(C):
				if A[r][c] == 1:
					groups.append((dfs(r, c, []), marker))
					marker += 1
		groups = sorted(groups, key=lambda x: len(x[0]))
		(src_group, src_marker) = groups[0]
		q = deque([(row, col, 0) for (row, col) in src_group])
		target = set(groups[1][0])
		while q:
			(row, col, curr_distance) = q.pop()
			if (row, col) in target:
				return curr_distance - 1
			for (dr, dc) in directions:
				(new_row, new_col) = (row + dr, col + dc)
				if 0 <= new_row < R and 0 <= new_col < C and (A[new_row][new_col] != src_marker):
					q.appendleft((new_row, new_col, curr_distance + 1))
					A[new_row][new_col] = src_marker
		return -1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(m, n) = (len(A) if A else 0, len(A[0]) if A else 0)
		(p, q) = (-1, -1)

		def neighbors(r, c):
			for (nr, nc) in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
				if nr in range(m) and nc in range(n):
					yield (nr, nc)
		done = set()
		components = []
		for (i, j) in product(list(range(m)), list(range(n))):
			if A[i][j] == 1:
				if (i, j) not in done:
					stack = [(i, j)]
					seen = {(i, j)}
					while stack:
						node = stack.pop()
						for (p, q) in neighbors(*node):
							if (p, q) not in seen:
								if A[p][q] == 1:
									seen.add((p, q))
									stack.append((p, q))
					done |= seen
					components.append(seen)
		(source, target) = components
		heap = []
		for (i, j) in source:
			heappush(heap, (0, (i, j)))
		done = set(source)
		while heap:
			(dist, (i, j)) = heappop(heap)
			if (i, j) in target:
				return dist - 1
			for (r, s) in neighbors(i, j):
				if A[r][s] not in source and (r, s) not in done:
					done.add((r, s))
					heappush(heap, (dist + 1, (r, s)))


class Solution:

	def find_island(self, i, j):
		self.island.append([i, j])
		self.grid[i][j] = -1
		D = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		for d in D:
			if i + d[0] in range(self.m) and j + d[1] in range(self.n) and (self.grid[i + d[0]][j + d[1]] == 1):
				self.find_island(i + d[0], j + d[1])

	def expand_island(self):
		D = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		while len(self.island) > 0:
			[i, j] = self.island.pop(0)
			depth = abs(self.grid[i][j])
			for d in D:
				if i + d[0] in range(self.m) and j + d[1] in range(self.n):
					if self.grid[i + d[0]][j + d[1]] == 1:
						return depth - 1
					if self.grid[i + d[0]][j + d[1]] == 0:
						self.island.append([i + d[0], j + d[1]])
						self.grid[i + d[0]][j + d[1]] = -1 * (depth + 1)
		return self.m + self.n - 1

	def shortestBridge(self, A: List[List[int]]) -> int:
		self.grid = A
		self.m = len(A)
		self.n = len(A[0])
		self.island = []
		for i in range(self.m):
			for j in range(self.n):
				if self.grid[i][j] == 1 and len(self.island) == 0:
					self.find_island(i, j)
		res = self.expand_island()
		return res


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		i1 = []
		m = len(A)
		n = len(A[0])
		vis = [[False for _ in range(n)] for _ in range(m)]

		def check(x, y):
			return x >= 0 and x < m and (y >= 0) and (y < n)
		dx = [0, -1, 0, 1]
		dy = [1, 0, -1, 0]

		def dfs(p_x, p_y, i):
			vis[p_x][p_y] = True
			i.append((p_x, p_y))
			for j in range(4):
				(c_x, c_y) = (p_x + dx[j], p_y + dy[j])
				if check(c_x, c_y) and (not vis[c_x][c_y]):
					if A[c_x][c_y]:
						dfs(c_x, c_y, i)
		conn = 0
		for i in range(m):
			for j in range(n):
				if not vis[i][j] and A[i][j]:
					if conn == 0:
						dfs(i, j, i1)
					elif conn == 1:
						break
					conn += 1
			if conn == 1:
				break
		q = deque()
		d = [[float('inf') for _ in range(n)] for _ in range(m)]
		for v in i1:
			q.append(v)
			d[v[0]][v[1]] = 0
		ans = float('inf')
		while q:
			(s_x, s_y) = (q[0][0], q[0][1])
			q.popleft()
			for i in range(4):
				(c_x, c_y) = (s_x + dx[i], s_y + dy[i])
				if check(c_x, c_y):
					if d[c_x][c_y] > d[s_x][s_y] + 1:
						d[c_x][c_y] = d[s_x][s_y] + 1
						q.append((c_x, c_y))
						if A[c_x][c_y]:
							ans = min(ans, d[c_x][c_y] - 1)
		return ans


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		self.A = A
		self.R = len(self.A)
		self.C = len(self.A[0])
		p = self.findGround()
		if p == None:
			return -1
		self.firstIsland = set()
		self.embraceIsland(p)
		return self.bfs()

	def findGround(self):
		for i in range(0, self.R):
			for j in range(0, self.C):
				if self.isGround((i, j)):
					return (i, j)
		return None

	def isGround(self, p):
		return self.A[p[0]][p[1]] == 1

	def inGrid(self, p):
		if not 0 <= p[0] < self.R:
			return False
		if not 0 <= p[1] < self.C:
			return False
		return True

	def getNeis(self, p):
		neis = []
		neis.append((p[0] + 1, p[1]))
		neis.append((p[0] - 1, p[1]))
		neis.append((p[0], p[1] + 1))
		neis.append((p[0], p[1] - 1))
		return neis

	def embraceIsland(self, p):
		self.firstIsland.add(p)
		for nei in self.getNeis(p):
			if self.inGrid(nei) and self.isGround(nei) and (nei not in self.firstIsland):
				self.embraceIsland(nei)

	def bfs(self):
		q = collections.deque()
		visited = set()
		for p in self.firstIsland:
			q.appendleft((p, 0))
		while q:
			(node, dist) = q.pop()
			if self.isGround(node) and node not in self.firstIsland:
				return dist - 1
			if node in visited:
				continue
			visited.add(node)
			for nei in self.getNeis(node):
				if self.inGrid(nei) and nei not in visited:
					q.appendleft((nei, dist + 1))
		return -1


class Solution:

	def paint(self, A, i, j):
		if i >= len(A) or i < 0 or j < 0 or (j >= len(A[0])) or (A[i][j] == 0) or (A[i][j] == 2):
			return
		A[i][j] = 2
		for nb in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
			self.paint(A, i + nb[0], j + nb[1])

	def expand(self, A, i, j, color):
		if i >= len(A) or i < 0 or j < 0 or (j >= len(A[0])):
			return False
		if A[i][j] == 0:
			A[i][j] = color + 1
		return A[i][j] == 1

	def shortestBridge(self, A: List[List[int]]) -> int:
		if not A:
			return 0
		(m, n, flag) = (len(A), len(A[0]), False)
		for i in range(m):
			if flag:
				break
			for j in range(n):
				if A[i][j] == 1:
					self.paint(A, i, j)
					flag = True
					break
		for color in range(2, 2 + m + n + 1):
			for i in range(m):
				for j in range(n):
					if A[i][j] == color and (self.expand(A, i - 1, j, color) or self.expand(A, i, j + 1, color) or self.expand(A, i + 1, j, color) or self.expand(A, i, j - 1, color)):
						return color - 2


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		u = {(i, j): (i, j) for i in range(len(A)) for j in range(len(A[0])) if A[i][j]}

		def head(p):
			if u[p] == p:
				return p
			h = head(u[p])
			u[p] = h
			return h

		def union(p1, p2):
			u[head(p2)] = head(p1)
		for (i, row) in enumerate(A):
			for (j, v) in enumerate(row):
				if not v:
					continue
				if i and A[i - 1][j]:
					union((i - 1, j), (i, j))
				if j and A[i][j - 1]:
					union((i, j - 1), (i, j))
		grps = {p1: set() for (p1, p2) in list(u.items()) if p1 == p2}
		for p in list(u.keys()):
			grps[head(p)].add(p)
		grps = list(grps.values())
		s = 0
		(layer, target) = grps
		while layer:
			new_layer = []
			for (x, y) in layer:
				for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
					nx = x + dx
					ny = y + dy
					if nx < 0 or nx >= len(A) or ny < 0 or (ny >= len(A[0])):
						continue
					if A[nx][ny] == 1 and (nx, ny) in target:
						return s
					if not A[nx][ny]:
						new_layer.append((nx, ny))
						A[nx][ny] = -1
			s += 1
			layer = new_layer
		return


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		r = len(A)
		c = len(A[0])
		dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		dist = [[float('inf') for j in range(c)] for i in range(r)]
		island1 = set()
		island2 = set()

		def dfs(x, y, island):
			island.add((x, y))
			for (i, j) in dirs:
				if 0 <= x + i < r and 0 <= y + j < c and (A[x + i][y + j] == 1) and ((x + i, y + j) not in island):
					dfs(x + i, y + j, island)
		for i in range(r):
			for j in range(c):
				if A[i][j] == 1:
					if len(island1) == 0:
						dfs(i, j, island1)
					elif (i, j) not in island1:
						dfs(i, j, island2)
		q = collections.deque(list(island1))
		d = 1
		res = float('inf')
		while q:
			size = len(q)
			for i in range(size):
				(x, y) = q.popleft()
				for (i, j) in dirs:
					if 0 <= x + i < r and 0 <= y + j < c:
						if A[x + i][y + j] == 0 and d < dist[x + i][y + j]:
							q.append((x + i, y + j))
							dist[x + i][y + j] = d
						if (x + i, y + j) in island2:
							res = min(res, d - 1)
			d += 1
		return res


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		gather = []
		for y in range(len(A)):
			for x in range(len(A[y])):
				if A[y][x] == 1:
					A[y][x] = 2
					gather.append((x, y, 0))
					break
			if gather:
				break
		dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		seen = set([gather[0]])
		while gather:
			frontier = []
			for (x, y, _) in gather:
				for (dx, dy) in dirs:
					(xx, yy) = (x + dx, y + dy)
					if (xx, yy, 0) in seen:
						continue
					if 0 <= yy < len(A) and 0 <= xx < len(A[yy]) and (A[yy][xx] == 1):
						A[yy][xx] = 2
						seen.add((xx, yy, 0))
						frontier.append((xx, yy, 0))
			gather = frontier
		bfs = list(seen)
		while bfs:
			frontier = []
			for (x, y, n) in bfs:
				A[y][x] = 2
				for (dx, dy) in dirs:
					(xx, yy) = (x + dx, y + dy)
					if 0 <= yy < len(A) and 0 <= xx < len(A[yy]):
						if A[yy][xx] == 1:
							return n
						elif A[yy][xx] == 0:
							A[yy][xx] = 2
							frontier.append((xx, yy, n + 1))
			bfs = frontier
		return -1


import queue

def isOk(x, y, m, n):
	return x >= 0 and y >= 0 and (x < m) and (y < n)

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		m = len(A)
		n = len(A[0])
		visited = [[False for _ in range(n)] for _ in range(m)]

		def dfs(start):
			island = []
			(x, y) = start
			visited[x][y] = True
			stack = [start]
			while stack:
				(x, y) = stack.pop()
				island.append((x, y))
				xRows = [0, 0, -1, 1]
				yCols = [-1, 1, 0, 0]
				for i in range(4):
					new_x = x + xRows[i]
					new_y = y + yCols[i]
					if isOk(new_x, new_y, m, n) and (not visited[new_x][new_y]) and (A[new_x][new_y] == 1):
						stack.append((new_x, new_y))
						visited[new_x][new_y] = True
			return island
		islands = []
		for i in range(m):
			for j in range(n):
				if not visited[i][j] and A[i][j] == 1:
					island = dfs((i, j))
					islands.append(island)
		(source_island, target_island) = islands
		print(source_island)
		print(target_island)
		target_island = set(target_island)
		visited = [[False for _ in range(n)] for _ in range(m)]

		def bfs(source_island, target_island, visited):
			q = queue.Queue()
			for start in source_island:
				(x, y) = start
				q.put((x, y, 0))
			while q.qsize() > 0:
				u = q.get()
				(x, y, w) = u
				xRows = [-1, 1, 0, 0]
				yCols = [0, 0, -1, 1]
				for i in range(4):
					new_x = x + xRows[i]
					new_y = y + yCols[i]
					if isOk(new_x, new_y, m, n) and (not visited[new_x][new_y]):
						if (new_x, new_y) in target_island:
							return w
						visited[new_x][new_y] = True
						q.put((new_x, new_y, w + 1))
		return bfs(source_island, target_island, visited)


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		options = [[-1, 0], [1, 0], [0, 1], [0, -1]]
		flip_req = float('inf')
		isl_one_coords = set()

		def get_all(i, j):
			nonlocal flip_req, isl_one_coords, options
			for opt in options:
				new_coord = (i + opt[0], j + opt[1])
				if 0 <= new_coord[0] < len(A) and 0 <= new_coord[1] < len(A[0]):
					if A[new_coord[0]][new_coord[1]] and (not new_coord in isl_one_coords):
						isl_one_coords.add(new_coord)
						get_all(new_coord[0], new_coord[1])

		def bfs():
			nonlocal flip_req, isl_one_coords, options
			dist = 0
			level = set([x for x in isl_one_coords])
			next_level = set()
			while level:
				for coords in level:
					for opt in options:
						new_coord = (coords[0] + opt[0], coords[1] + opt[1])
						if 0 <= new_coord[0] < len(A) and 0 <= new_coord[1] < len(A[0]) and (not new_coord in isl_one_coords):
							if A[new_coord[0]][new_coord[1]]:
								return dist
							if not A[new_coord[0]][new_coord[1]]:
								isl_one_coords.add(new_coord)
								next_level.add(new_coord)
				dist += 1
				(level, next_level) = (next_level, set())
				print((level, next_level, isl_one_coords))
		for i in range(len(A)):
			for j in range(len(A[0])):
				if A[i][j]:
					isl_one_coords.add((i, j))
					get_all(i, j)
					return bfs()


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(R, C) = (len(A), len(A[0]))
		dist = [[float('inf')] * C for _ in range(R)]
		directs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		src = None
		for r in range(R):
			for c in range(C):
				if A[r][c] == 1:
					dist[r][c] = 0
					src = (r, c)
				if src:
					break
			if src:
				break
		queue = [(0, r, c)]
		while queue:
			(d, r, c) = heapq.heappop(queue)
			for (dr, dc) in directs:
				(nr, nc) = (r + dr, c + dc)
				if not (0 <= nr < R and 0 <= nc < C):
					continue
				enqueue = False
				if A[nr][nc] == 1 and A[r][c] == 1:
					if d < dist[nr][nc]:
						dist[nr][nc] = d
						enqueue = True
				elif d + 1 < dist[nr][nc]:
					dist[nr][nc] = d + 1
					enqueue = True
				if enqueue:
					heapq.heappush(queue, (dist[nr][nc], nr, nc))
		ans = float('inf')
		for r in range(R):
			for c in range(C):
				if A[r][c] == 1 and dist[r][c] > 0:
					ans = min(ans, dist[r][c] - 1)
		return ans


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		queue = []

		def markIsland2(i, j):
			if i < 0 or i >= len(A) or j < 0 or (j >= len(A)):
				return False
			if A[i][j] == 2:
				return False
			if A[i][j] == 0:
				return True
			A[i][j] = 2
			shore = False
			for (x, y) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
				shore |= markIsland2(i + x, j + y)
			if shore:
				queue.append((i, j))
			return False
		flag = False
		for i in range(len(A)):
			if flag:
				break
			for j in range(len(A)):
				if A[i][j] == 1:
					markIsland2(i, j)
					flag = True
					break

		def BFS(i, j):
			queue.append((i, j))
			for (x, y) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
				if 0 <= i + x < len(A) and 0 <= j + y < len(A):
					if A[i + x][j + y] == 1:
						return True
					elif A[i + x][j + y] == 0:
						A[i + x][j + y] = 2
						queue.append((i + x, j + y))
			else:
				return False
		cnt = 0
		while queue:
			size = len(queue)
			for _ in range(size):
				(i, j) = queue.pop(0)
				if BFS(i, j):
					return cnt
			cnt += 1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def dfs(A, i, j):
			if i < 0 or j < 0 or i > len(A) - 1 or (j > len(A[0]) - 1):
				return
			if visited[i][j] or A[i][j] == 0:
				return
			visited[i][j] = True
			queue.append((i, j))
			for k in range(4):
				rr = i + rowVector[k]
				cc = j + colVector[k]
				dfs(A, rr, cc)
		visited = [[False for i in range(len(A[0]))] for j in range(len(A))]
		rowVector = [1, -1, 0, 0]
		colVector = [0, 0, 1, -1]
		queue = []
		found = False
		for i in range(len(A)):
			if found:
				break
			for j in range(len(A[0])):
				if A[i][j] == 1:
					dfs(A, i, j)
					found = True
					break
		count = 0
		while queue:
			subQ = []
			while queue:
				temp = queue.pop(0)
				for k in range(4):
					i = temp[0] + rowVector[k]
					j = temp[1] + colVector[k]
					if i < 0 or j < 0 or i > len(A) - 1 or (j > len(A[0]) - 1) or visited[i][j]:
						continue
					if A[i][j] == 1:
						return count
					subQ.append((i, j))
					visited[i][j] = True
			queue = subQ
			count += 1
		return -1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		if len(A) == 0:
			return 0
		m = len(A)
		n = len(A[0])
		queue = []
		component = 2
		for i in range(m):
			for j in range(n):
				if A[i][j] == 1:
					self.dfs(i, j, A, queue, component)
					print(A)
					component += 1
		directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		while queue:
			(path, x, y) = queue.pop(0)
			if A[x][y] == 3:
				continue
			for (dx, dy) in directions:
				if x + dx < 0 or y + dy < 0 or x + dx >= m or (y + dy >= n):
					continue
				if A[x + dx][y + dy] == 3:
					return path
				if A[x + dx][y + dy] == 0:
					A[x + dx][y + dy] = 2
					queue.append((path + 1, x + dx, y + dy))

	def dfs(self, i, j, grid, queue, component):
		queue.append((0, i, j))
		grid[i][j] = component
		stack = [(i, j)]
		directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		while stack:
			(x, y) = stack.pop()
			for (dx, dy) in directions:
				if x + dx < 0 or y + dy < 0 or x + dx >= len(grid) or (y + dy >= len(grid[0])):
					continue
				if grid[x + dx][y + dy] == 1:
					queue.append((0, x + dx, y + dy))
					stack.append((x + dx, y + dy))
					grid[x + dx][y + dy] = component


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(R, C) = (len(A), len(A[0]))

		def getNeighbors(curr_points):
			neighbors = set()
			for (i, j) in curr_points:
				for (row, col) in [(i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1)]:
					if 0 <= row < R and 0 <= col < C:
						neighbors.add((row, col))
			return neighbors

		def get_islands():

			def dfs(pos, visited):
				(i, j) = pos
				if i >= R or i < 0 or j >= C or (j < 0) or (A[i][j] == 0) or (pos in visited):
					return
				visited.add(pos)
				dfs((i + 1, j), visited)
				dfs((i - 1, j), visited)
				dfs((i, j + 1), visited)
				dfs((i, j - 1), visited)
			(island1, island2) = (set(), set())
			for i in range(R):
				for j in range(C):
					if A[i][j] == 1:
						if not island1:
							dfs((i, j), island1)
						elif not island2 and (i, j) not in island1:
							dfs((i, j), island2)
			return (island1, island2)
		(island1, island2) = get_islands()
		min_distance = 0
		while True:
			neighbors = getNeighbors(island1)
			for neighbor in neighbors:
				if neighbor in island2:
					return min_distance
				island1.add(neighbor)
			min_distance += 1
		return min_distance

	def dist(self, x, y):
		return abs(x[0] - y[0]) + abs(x[1] - y[1]) - 1


import numpy as np

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(self.R, self.C) = (len(A), len(A[0]))
		self.queue = []
		self.visited = []
		for k in range(self.R):
			self.visited.append([0] * self.C)
		count = 0
		for rr in range(self.R):
			for cc in range(self.C):
				if A[rr][cc] == 1:
					self.dfs(A, rr, cc)
					count = 1
				if count > 0:
					break
			if count > 0:
				break
		while self.queue:
			node_visit = self.queue.pop(0)
			q_step = node_visit.step
			for (r_srch, c_srch) in self.dirs(A, node_visit.r, node_visit.c):
				if A[r_srch][c_srch] == 0 and self.visited[r_srch][c_srch] == 0:
					self.queue.append(self.node(q_step + 1, r_srch, c_srch))
					self.visited[r_srch][c_srch] = 1
				if A[r_srch][c_srch] == 1:
					return q_step

	def dirs(self, A, r, c) -> int:
		dir_list = []
		for (rr, cc) in [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]]:
			if rr >= 0 and cc >= 0 and (rr < self.R) and (cc < self.C):
				dir_list.append([rr, cc])
		return dir_list

	def dfs(self, A, r, c):
		if A[r][c] != 1:
			return
		A[r][c] = 2
		self.queue.append(self.node(0, r, c))
		self.visited[r][c] = 1
		for (r_srch, c_srch) in self.dirs(A, r, c):
			self.dfs(A, r_srch, c_srch)

	class node:

		def __init__(self, step, r, c):
			self.step = step
			self.r = r
			self.c = c


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		m = len(A)
		n = len(A[0])
		visited = [[False] * n for _ in range(m)]
		directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]

		def findFirstIsland():
			for r in range(m):
				for c in range(n):
					if A[r][c] == 1:
						return (r, c)
		queue = deque()

		def dfs(r, c):
			if visited[r][c]:
				return
			visited[r][c] = True
			if isBoundary(r, c):
				queue.append((r, c, -1))
			for (dr, dc) in directions:
				(nr, nc) = (r + dr, c + dc)
				if not (0 <= nr < m and 0 <= nc < n):
					continue
				if A[nr][nc] == 1 and (not visited[nr][nc]):
					dfs(nr, nc)

		def isBoundary(r, c):
			for (dr, dc) in directions:
				(nr, nc) = (r + dr, c + dc)
				if not (0 <= nr < m and 0 <= nc < n):
					continue
				if A[nr][nc] == 0:
					return True
			return False
		(sr, sc) = findFirstIsland()
		dfs(sr, sc)
		visited2 = [[False] * n for _ in range(m)]
		while queue:
			(r, c, d) = queue.popleft()
			visited2[r][c] = True
			if not visited[r][c] and A[r][c] == 1:
				return d
			for (dr, dc) in directions:
				(nr, nc) = (r + dr, c + dc)
				if not (0 <= nr < m and 0 <= nc < n):
					continue
				if not visited2[nr][nc]:
					visited2[nr][nc] = True
					queue.append((nr, nc, d + 1))
		return 1


from collections import deque

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def get_edges(visited, A, i, j, isle):
			dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
			queue = deque([(i, j)])
			visited[i][j] = True
			edges = set()
			while queue:
				edge = 0
				(ci, cj) = queue.popleft()
				for (di, dj) in dirs:
					x = ci + di
					y = cj + dj
					if 0 <= x < m and 0 <= y < n and (A[x][y] == 1) and (not visited[x][y]):
						queue.append((x, y))
						visited[x][y] = True
					elif 0 <= x < m and 0 <= y < n and (A[x][y] == 0):
						edge = 1
				if edge:
					edges.add((ci, cj))
			return edges

		def manattan(a, b, c, d):
			return abs(a - c) + abs(b - d) - 1
		visited = [[0] * len(A[0]) for i in range(len(A))]
		m = len(A)
		n = len(A[0])
		edge_islands = []
		counts = 0
		for ii in range(m):
			for jj in range(n):
				if A[ii][jj] == 1 and (not visited[ii][jj]):
					counts += 1
					edge_islands.append(get_edges(visited, A, ii, jj, counts))
		isle1 = edge_islands[0]
		isle2 = edge_islands[1]
		mins = float('inf')
		for i1 in isle1:
			for i2 in isle2:
				mins = min(mins, manattan(i1[0], i1[1], i2[0], i2[1]))
		return mins


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		M = len(A)
		N = len(A[0])
		q = collections.deque()
		i0 = None
		j0 = None
		for i in range(M):
			for j in range(N):
				if A[i][j] == 1:
					(i0, j0) = (i, j)
					break
			if i0 is not None:
				break
		q.append((i0, j0))
		A[i0][j0] = 2
		vis = set()
		dirs_lst = [(-1, 0), (1, 0), (0, 1), (0, -1)]
		boarder = set()
		while q:
			(i, j) = q.popleft()
			for (di, dj) in dirs_lst:
				ni = i + di
				nj = j + dj
				if ni < 0 or ni > M - 1 or nj < 0 or (nj > N - 1):
					boarder.add((i, j))
					continue
				if A[ni][nj] == 0:
					boarder.add((i, j))
					continue
				if (ni, nj) in vis:
					continue
				A[ni][nj] = 2
				vis.add((ni, nj))
				q.append((ni, nj))
		vis.clear()
		for (i, j) in boarder:
			q.append((i, j, 0))
		res = math.inf
		while q:
			(i, j, nsteps) = q.popleft()
			for (di, dj) in dirs_lst:
				ni = i + di
				nj = j + dj
				if ni < 0 or ni > M - 1 or nj < 0 or (nj > N - 1):
					continue
				if (ni, nj) in vis:
					continue
				if A[ni][nj] == 1:
					res = min(res, nsteps)
					continue
				vis.add((ni, nj))
				q.append((ni, nj, nsteps + 1))
		return res


class Solution:

	def shortestBridge(self, mat: List[List[int]]) -> int:
		R = len(mat)
		C = len(mat and mat[0])

		def expand(island, other):
			new = set()
			for (r, c) in island:
				for (nr, nc) in ((r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)):
					if R > nr >= 0 <= nc < C:
						if (nr, nc) in other:
							return True
						if mat[nr][nc] == 0:
							mat[nr][nc] = 2
							new.add((nr, nc))
			island.update(new)

		def findIsland(r, c, island):
			island.add((r, c))
			mat[r][c] = 2
			for (nr, nc) in ((r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)):
				if R > nr >= 0 <= nc < C and mat[nr][nc] == 1 and ((nr, nc) not in island):
					findIsland(nr, nc, island)
		islands = []
		for r in range(R):
			for c in range(C):
				if mat[r][c] == 1:
					island = set()
					findIsland(r, c, island)
					islands.append(island)
		ans = 0
		while True:
			if expand(*islands):
				return ans
			ans += 1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(R, C) = (len(A), len(A[0]))
		dist = [[float('inf')] * C for _ in range(R)]
		directs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

		def findSrc():
			for r in range(R):
				for c in range(C):
					if A[r][c] == 1:
						return (r, c)
		(r, c) = findSrc()
		dist[r][c] = 0
		queue = [(0, r, c)]

		def neighbors(r, c):
			for (nr, nc) in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
				if 0 <= nr < R and 0 <= nc < C:
					yield (nr, nc)
		while queue:
			(d, r, c) = heapq.heappop(queue)
			for (nr, nc) in neighbors(r, c):
				enqueue = False
				if A[nr][nc] == 1 and A[r][c] == 1:
					if d < dist[nr][nc]:
						dist[nr][nc] = d
						enqueue = True
				elif d + 1 < dist[nr][nc]:
					dist[nr][nc] = d + 1
					enqueue = True
				if enqueue:
					heapq.heappush(queue, (dist[nr][nc], nr, nc))
		ans = float('inf')
		for r in range(R):
			for c in range(C):
				if A[r][c] == 1 and dist[r][c] > 0:
					ans = min(ans, dist[r][c] - 1)
		return ans


from math import sqrt

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def get_islands(A):
			island_one = set()
			for i in range(len(A)):
				for j in range(len(A[0])):
					if A[i][j] == 1 and (i, j) not in island_one:
						if not island_one:
							island_one = make_island(A, i, j, set())
						else:
							return (island_one, make_island(A, i, j, set()))

		def make_island(A, i, j, visited):
			visited.add((i, j))
			up = A[i][j + 1] if j < len(A[0]) - 1 else 0
			down = A[i][j - 1] if j > 0 else 0
			left = A[i - 1][j] if i > 0 else 0
			right = A[i + 1][j] if i < len(A) - 1 else 0
			if up and (i, j + 1) not in visited:
				make_island(A, i, j + 1, visited)
			if down and (i, j - 1) not in visited:
				make_island(A, i, j - 1, visited)
			if left and (i - 1, j) not in visited:
				make_island(A, i - 1, j, visited)
			if right and (i + 1, j) not in visited:
				make_island(A, i + 1, j, visited)
			return visited

		def find_shortest_bridge(A, i, j, start_island, global_dist_map):
			queue = [(i, j)]
			dist_map = {(i, j): 0}
			while queue:
				(i, j) = queue.pop(0)
				neighbors = []
				if (i, j + 1) not in start_island and j < len(A[0]) - 1:
					neighbors.append((i, j + 1))
				if (i, j - 1) not in start_island and j > 0:
					neighbors.append((i, j - 1))
				if (i - 1, j) not in start_island and i > 0:
					neighbors.append((i - 1, j))
				if (i + 1, j) not in start_island and i < len(A) - 1:
					neighbors.append((i + 1, j))
				for neighbor in neighbors:
					(n_i, n_j) = neighbor
					if A[n_i][n_j] == 1:
						return dist_map[i, j] + 1
					if neighbor not in global_dist_map or global_dist_map[neighbor] > dist_map[i, j] + 1:
						queue.append(neighbor)
						global_dist_map[neighbor] = dist_map[neighbor] = dist_map[i, j] + 1
			return False

		def find_shortest_pair(island1, island2):
			min_distance = len(A) * len(A[0])
			shortest_coords = None
			for coords1 in island1:
				for coords2 in island2:
					distance_between = sqrt((coords2[0] - coords1[0]) ** 2 + (coords2[1] - coords1[1]) ** 2)
					if distance_between < min_distance:
						min_distance = distance_between
						shortest_coords = (coords1, coords2)
			return shortest_coords
		(first_island, second_island) = get_islands(A)
		min_island = first_island if len(first_island) < len(second_island) else second_island
		shortest_bridge = len(A) * len(A[0])
		global_dist_map = {}
		for island in min_island:
			(i, j) = island
			shortest_bridge_here = find_shortest_bridge(A, i, j, min_island, global_dist_map)
			if shortest_bridge_here:
				shortest_bridge = min(shortest_bridge, shortest_bridge_here)
		return shortest_bridge - 1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def get_islands(A):
			island_one = set()
			for i in range(len(A)):
				for j in range(len(A[0])):
					if A[i][j] == 1 and (i, j) not in island_one:
						if not island_one:
							island_one = make_island(A, i, j, set())
						else:
							return (island_one, make_island(A, i, j, set()))

		def make_island(A, i, j, visited):
			visited.add((i, j))
			up = A[i][j + 1] if j < len(A[0]) - 1 else 0
			down = A[i][j - 1] if j > 0 else 0
			left = A[i - 1][j] if i > 0 else 0
			right = A[i + 1][j] if i < len(A) - 1 else 0
			if up and (i, j + 1) not in visited:
				make_island(A, i, j + 1, visited)
			if down and (i, j - 1) not in visited:
				make_island(A, i, j - 1, visited)
			if left and (i - 1, j) not in visited:
				make_island(A, i - 1, j, visited)
			if right and (i + 1, j) not in visited:
				make_island(A, i + 1, j, visited)
			return visited

		def find_shortest_bridge(A, i, j, start_island, global_dist_map):
			queue = [(i, j)]
			dist_map = {(i, j): 0}
			while queue:
				(i, j) = queue.pop(0)
				neighbors = []
				if (i, j + 1) not in start_island and j < len(A[0]) - 1:
					neighbors.append((i, j + 1))
				if (i, j - 1) not in start_island and j > 0:
					neighbors.append((i, j - 1))
				if (i - 1, j) not in start_island and i > 0:
					neighbors.append((i - 1, j))
				if (i + 1, j) not in start_island and i < len(A) - 1:
					neighbors.append((i + 1, j))
				for neighbor in neighbors:
					(n_i, n_j) = neighbor
					if A[n_i][n_j] == 1:
						return dist_map[i, j] + 1
					if neighbor not in global_dist_map or global_dist_map[neighbor] > dist_map[i, j] + 1:
						queue.append(neighbor)
						global_dist_map[neighbor] = dist_map[neighbor] = dist_map[i, j] + 1
			return False
		(first_island, second_island) = get_islands(A)
		min_island = first_island if len(first_island) < len(second_island) else second_island
		shortest_bridge = len(A) * len(A[0])
		global_dist_map = {}
		for island in min_island:
			(i, j) = island
			shortest_bridge_here = find_shortest_bridge(A, i, j, min_island, global_dist_map)
			if shortest_bridge_here:
				shortest_bridge = min(shortest_bridge, shortest_bridge_here)
		return shortest_bridge - 1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		self.map = A
		self.rows = len(self.map)
		self.cols = len(self.map[0])
		self.queue = []
		self.src = 2
		self.dst = 3
		for island_index in [self.src, self.dst]:
			add_to_queue = island_index == self.src
			self.exploreIsland(island_index, add_to_queue)
		self.queue_index = 0
		return self.bridgeBFS()

	def exploreIsland(self, index, add):
		(row, col) = self.getIslandLocation()
		self.islandDFS(index, row, col, add)

	def getIslandLocation(self):
		for row in range(self.rows):
			for col in range(self.cols):
				if self.map[row][col] == 1:
					return (row, col)

	def islandDFS(self, index, row, col, add):
		if self.validCoords(row, col) and self.map[row][col] == 1:
			self.map[row][col] = index
			if add:
				self.queue.append((row, col, 0))
			for search_row in range(row - 1, row + 2, 2):
				self.islandDFS(index, search_row, col, add)
			for search_col in range(col - 1, col + 2, 2):
				self.islandDFS(index, row, search_col, add)

	def validCoords(self, row, col):
		if row < 0 or row >= self.rows:
			return False
		if col < 0 or col >= self.cols:
			return False
		return True

	def bridgeBFS(self):
		while self.queue_index < len(self.queue):
			(row, col, dist) = self.queue[self.queue_index]
			self.queue_index += 1
			for search_row in range(row - 1, row + 2, 2):
				if self.processCoord(search_row, col, dist):
					return dist
			for search_col in range(col - 1, col + 2, 2):
				if self.processCoord(row, search_col, dist):
					return dist

	def processCoord(self, row, col, dist):
		if not self.validCoords(row, col):
			return False
		if self.map[row][col] == self.dst:
			return True
		elif self.map[row][col] != self.src:
			self.queue.append((row, col, dist + 1))
			self.map[row][col] = self.src
		return False


class Solution:

	def dfs(self, A, i, j, replace):
		if i < 0 or i >= len(A) or j < 0 or (j >= len(A[0])):
			return
		if A[i][j] == 0 or A[i][j] == replace:
			return
		A[i][j] = replace
		r = self.dfs(A, i + 1, j, replace)
		d = self.dfs(A, i, j + 1, replace)
		u = self.dfs(A, i - 1, j, replace)
		l = self.dfs(A, i, j - 1, replace)
		return

	def find(self, A, i, j, old):
		if i < 0 or i >= len(A) or j < 0 or (j >= len(A[0])):
			return False
		if A[i][j] == -1:
			return True
		if A[i][j] == 0:
			A[i][j] = old + 1
			return False
		if A[i][j] == old + 1:
			return False
		A[i][j] = old + 1
		return self.find(A, i + 1, j, old) or self.find(A, i - 1, j, old) or self.find(A, i, j + 1, old) or self.find(A, i, j - 1, old)

	def shortestBridge(self, A: List[List[int]]) -> int:
		iindex = 0
		(i, j) = (0, 0)
		replace = -1
		start = ()
		while i < len(A):
			j = 0
			while j < len(A[0]):
				if A[i][j] == 1:
					self.dfs(A, i, j, replace)
					iindex += 1
					replace = -2
					start = (i, j)
				j += 1
			i += 1
		old = 1
		while True:
			if self.find(A, start[0], start[1], old):
				break
			old += 1
		return old - 1


import collections

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		m = len(A)
		n = len(A[0])

		def neighbors(r, c):
			for (nr, nc) in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
				if 0 <= nr < m and 0 <= nc < n:
					yield (nr, nc)
		seen = set()
		islands = {2: set(), 3: set()}

		def color_island(r, c, island_id):
			seen.add((r, c))
			if A[r][c] != 1:
				return
			A[r][c] = island_id
			islands[island_id].add((r, c))
			for (x, y) in neighbors(r, c):
				if (x, y) not in seen:
					color_island(x, y, island_id)
		islands_found = 0
		for r in range(m):
			if islands_found == 2:
				break
			for c in range(n):
				if islands_found == 2:
					break
				if A[r][c] == 1:
					islands_found += 1
					color_island(r, c, islands_found + 1)
		source = islands[2]
		target = islands[3]
		queue = collections.deque([(node, 0) for node in source])
		seen = source
		while queue:
			((r, c), d) = queue.popleft()
			if (r, c) in target:
				return d - 1
			for (x, y) in neighbors(r, c):
				if (x, y) not in seen:
					queue.append(((x, y), d + 1))
					seen.add((x, y))


class Solution:
	DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]]

	def shortestBridge(self, A: List[List[int]]) -> int:
		if not A:
			return 0
		(m, n) = (len(A), len(A[0]))
		queue = collections.deque()
		found = False
		for i in range(m):
			for j in range(n):
				if A[i][j] == 1:
					self.dfs(A, i, j, m, n, queue)
					found = True
					break
			if found:
				break
		bridge = 0
		while queue:
			for _ in range(len(queue)):
				(x, y) = queue.popleft()
				for d in self.DIRS:
					(next_x, next_y) = (x + d[0], y + d[1])
					if 0 <= next_x < m and 0 <= next_y < n and (A[next_x][next_y] == 0):
						queue.append((next_x, next_y))
						A[next_x][next_y] = 2
					if 0 <= next_x < m and 0 <= next_y < n and (A[next_x][next_y] == 1):
						return bridge
			bridge += 1
		return bridge

	def dfs(self, A, i, j, m, n, queue):
		if i < 0 or i >= m or j < 0 or (j >= n) or (A[i][j] != 1):
			return
		A[i][j] = 2
		queue.append((i, j))
		self.dfs(A, i + 1, j, m, n, queue)
		self.dfs(A, i - 1, j, m, n, queue)
		self.dfs(A, i, j + 1, m, n, queue)
		self.dfs(A, i, j - 1, m, n, queue)


from typing import List
from queue import Queue

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(first_island, second_island) = (set(), set())
		directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

		def get_all(x, y, island):
			if (x, y) in island or A[y][x] == 0:
				return
			island.add((x, y))
			for (dx, dy) in directions:
				if 0 <= x + dx < len(A[0]) and 0 <= y + dy < len(A):
					get_all(x + dx, y + dy, island)
		first_in = False
		for y in range(len(A)):
			for x in range(len(A[0])):
				if A[y][x] == 1:
					if not first_in:
						get_all(x, y, first_island)
						first_in = True
					elif (x, y) not in first_island:
						get_all(x, y, second_island)
						break
		visited = set()
		q = Queue()
		for (x, y) in first_island:
			q.put((x, y, 0))
		while not q.empty():
			(x, y, depth) = q.get()
			if (x, y) in second_island:
				return depth - 1
			for (dx, dy) in directions:
				(X, Y) = (x + dx, y + dy)
				if 0 <= X < len(A[0]) and 0 <= Y < len(A) and ((X, Y) not in visited):
					q.put((X, Y, depth + 1))
					visited.add((X, Y))


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		if not A:
			return 0
		m = len(A)
		n = len(A[0])

		def getnei(i, j):
			xy = []
			if i > 0:
				xy.append((i - 1, j))
			if j > 0:
				xy.append((i, j - 1))
			if i < m - 1:
				xy.append((i + 1, j))
			if j < m - 1:
				xy.append((i, j + 1))
			return xy

		def dfs1(i, j):
			if A[i][j] != 1:
				return
			A[i][j] = -1
			for (x, y) in getnei(i, j):
				dfs1(x, y)

		def bfs(i, j, dist_map, thresh):
			seen = set()
			q = collections.deque()
			q.append((i, j, 0))
			done = False
			while q and (not done):
				(ii, jj, depth) = q.popleft()
				if depth > thresh:
					done = True
					break
				for (x, y) in getnei(ii, jj):
					if (x, y) in dist_map and dist_map[x, y] < depth:
						continue
					if A[x][y] == -1:
						thresh = min(depth, thresh)
						done = True
						break
					elif A[x][y] == 0:
						if (x, y) in seen:
							continue
						seen.add((x, y))
						q.append((x, y, depth + 1))
			return thresh
		ans = math.inf
		is_second = False
		dist_map = {}
		for i in range(m):
			for j in range(n):
				if A[i][j] == 1:
					if not is_second:
						dfs1(i, j)
						is_second = True
					else:
						ans = min(ans, bfs(i, j, dist_map, ans))
		return ans


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		(islands, index) = ([set(), set()], -1)
		visited = set()

		def traverse(current):
			nonlocal A, islands, index, visited, directions
			islands[index].add(current)
			for d in directions:
				(new_i, new_j) = (current[0] + d[0], current[1] + d[1])
				if 0 <= new_i < len(A) and 0 <= new_j < len(A[0]) and ((new_i, new_j) not in visited) and (A[new_i][new_j] == 1):
					visited.add((new_i, new_j))
					traverse((new_i, new_j))
		for i in range(len(A)):
			for j in range(len(A[0])):
				if (i, j) not in visited and A[i][j] == 1:
					index += 1
					traverse((i, j))
		(one, two) = islands
		result = sys.maxsize
		for index in one:
			visited = set()
			queue = collections.deque([(index, 0)])
			while queue:
				current = queue.popleft()
				if current[1] >= result:
					break
				for d in directions:
					(new_i, new_j) = (current[0][0] + d[0], current[0][1] + d[1])
					if 0 <= new_i < len(A) and 0 <= new_j < len(A[0]) and ((new_i, new_j) not in one) and ((new_i, new_j) not in visited):
						if (new_i, new_j) in two:
							result = min(result, current[1])
							break
						visited.add((new_i, new_j))
						queue.append(((new_i, new_j), current[1] + 1))
		return result


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		rows = len(A)
		cols = len(A[0])

		def getNeighbors(i, j):
			for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
				if x >= 0 and x < rows and (y >= 0) and (y < cols):
					yield (x, y)

		def findComponents():
			visited = set()
			connectedNodes = [[] for i in range(2)]

			def findConnnectedComponent(i, j):
				visited.add((i, j))
				connectedNodes[connectedCompNumber].append((i, j))
				for (x, y) in getNeighbors(i, j):
					if (x, y) not in visited and A[x][y]:
						findConnnectedComponent(x, y)
			connectedCompNumber = -1
			for i in range(rows):
				for j in range(cols):
					if (i, j) not in visited and A[i][j] == 1:
						connectedCompNumber += 1
						findConnnectedComponent(i, j)
			return connectedNodes

		def findDistance() -> int:
			shortedDist = 1
			(source, target) = findComponents()
			queue = collections.deque()
			for s in source:
				queue.appendleft((s, 0))
			done = set()
			for s in source:
				done.add(s)
			while queue:
				(node, dist) = queue.pop()
				if node in target:
					return dist - 1
				for n in getNeighbors(*node):
					if n not in done:
						queue.appendleft((n, dist + 1))
						done.add(n)
		return findDistance()


import collections

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		found = False
		res = []
		for i in range(len(A)):
			for j in range(len(A[0])):
				if A[i][j] == 1:
					self.dfs(A, i, j, res)
					found = True
					break
			if found:
				break
		cnt = 0
		while res:
			tmp = []
			for (x, y) in res:
				for (dx, dy) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
					if 0 <= x + dx < len(A) and 0 <= y + dy < len(A[0]) and (A[x + dx][y + dy] != 2):
						if A[x + dx][y + dy] == 0:
							A[x + dx][y + dy] = 2
						if A[x + dx][y + dy] == 1:
							return cnt
						tmp.append([x + dx, y + dy])
			cnt += 1
			res = tmp
		return -1

	def dfs(self, A, i, j, res):
		if 0 <= i < len(A) and 0 <= j < len(A[0]) and (A[i][j] == 1):
			A[i][j] = 2
			res.append([i, j])
			self.dfs(A, i + 1, j, res)
			self.dfs(A, i - 1, j, res)
			self.dfs(A, i, j - 1, res)
			self.dfs(A, i, j + 1, res)


class Solution:

	def __init__(self):
		self.components = []
		self.comp = []
		self.seen = set()

	def isValid(self, r, c, A):
		if r < 0 or c < 0 or r >= len(A) or (c >= len(A)):
			return False
		return True

	def dfs(self, r, c, A):
		if not self.isValid(r, c, A) or (r, c) in self.seen or A[r][c] != 1:
			return
		self.comp.append((r, c))
		self.seen.add((r, c))
		self.dfs(r + 1, c, A)
		self.dfs(r - 1, c, A)
		self.dfs(r, c + 1, A)
		self.dfs(r, c - 1, A)

	def shortestBridge(self, A: List[List[int]]) -> int:
		for i in range(len(A)):
			for j in range(len(A[0])):
				if (i, j) not in self.seen and A[i][j] == 1:
					self.comp = []
					self.dfs(i, j, A)
					self.components.append(self.comp)
		(source, target) = self.components
		visited = set(source)
		queue = collections.deque([(node, 0) for node in source])
		while queue:
			(node, d) = queue.popleft()
			if node in target:
				return d - 1
			else:
				for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
					nr = node[0] + dr
					nc = node[1] + dc
					if (nr, nc) not in visited and self.isValid(nr, nc, A):
						queue.append(((nr, nc), d + 1))
						visited.add((nr, nc))
		return -1


class Solution:

	def __init__(self):
		self.islandA = []
		self.islandB = []
		self.maxRow = 0
		self.maxColumn = 0
		self.maps = []
		self.directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]

	def shortestBridge(self, A: List[List[int]]) -> int:
		self.maps = A
		self.maxRow = len(A) - 1
		self.maxColumn = len(A[0]) - 1
		for row in range(len(A)):
			for column in range(len(A[row])):
				value = A[row][column]
				if value == 1:
					if len(self.islandA) == 0:
						self.islandA = self.floodFill(A, self.islandA, row, column)
		stack = self.islandA
		print(stack)
		steps = 0
		while stack:
			temp = []
			for st in stack:
				for direction in self.directions:
					nextColumn = st[0] + direction[0]
					nextRow = st[1] + direction[1]
					if nextColumn < 0 or nextColumn > self.maxColumn or nextRow < 0 or (nextRow > self.maxRow) or (A[nextColumn][nextRow] == 2):
						continue
					if A[nextColumn][nextRow] == 1:
						return steps
					A[nextColumn][nextRow] = 2
					temp.append([nextColumn, nextRow])
			steps += 1
			stack = temp
		return 1

	def floodFill(self, A, island, row, column):
		if [row, column] not in island:
			island.append([row, column])
			A[row][column] = 2
		for direction in self.directions:
			nextColumn = column - direction[0]
			nextRow = row - direction[1]
			if nextColumn < 0 or nextColumn > self.maxColumn or nextRow < 0 or (nextRow > self.maxRow):
				continue
			if self.maps[nextRow][nextColumn] == 1 and [nextRow, nextColumn] not in island:
				island = self.floodFill(A, island, nextRow, nextColumn)
		return island


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		m = len(A)
		n = len(A[0])
		found = False
		for i in range(m):
			for j in range(n):
				if A[i][j] == 1:
					found = True
					break
			if found:
				break
		src = []
		q = []
		src.append((i, j))
		q.append((i, j))
		visited = [[False for _ in range(n)] for _ in range(m)]
		visited[i][j] = True
		while q:
			(curi, curj) = q.pop(0)
			for (nbori, nborj) in [(curi + 1, curj), (curi - 1, curj), (curi, curj + 1), (curi, curj - 1)]:
				if 0 <= nbori < m and 0 <= nborj < n:
					if not visited[nbori][nborj] and A[nbori][nborj] == 1:
						q.append((nbori, nborj))
						visited[nbori][nborj] = True
						src.append((nbori, nborj))
		found = False
		for i in range(m):
			for j in range(n):
				if A[i][j] == 1 and (not visited[i][j]):
					found = True
					break
			if found:
				break
		dest = []
		dest.append((i, j))
		q = []
		q.append((i, j))
		visited[i][j] = True
		while q:
			(curi, curj) = q.pop(0)
			for (nbori, nborj) in [(curi + 1, curj), (curi - 1, curj), (curi, curj + 1), (curi, curj - 1)]:
				if 0 <= nbori < m and 0 <= nborj < n:
					if not visited[nbori][nborj] and A[nbori][nborj] == 1:
						q.append((nbori, nborj))
						visited[nbori][nborj] = True
						dest.append((nbori, nborj))
		(source, target) = (src, dest)
		print(source, target)
		queue = collections.deque([(node, 0) for node in source])
		done = set(source)
		while queue:
			(node, d) = queue.popleft()
			(curi, curj) = node
			if node in target:
				return d - 1
			for nei in [(curi + 1, curj), (curi - 1, curj), (curi, curj + 1), (curi, curj - 1)]:
				if nei not in done:
					queue.append((nei, d + 1))
					done.add(nei)


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		minn = len(A) * 2
		visited = [[False for _ in range(len(A))] for _ in range(len(A))]
		label = 1
		found = False
		islands = {1: [], 2: []}

		def dfs(i, j):
			nonlocal A, visited, label, found
			if i < 0 or j < 0 or i + 1 > len(A) or (j + 1 > len(A)) or visited[i][j]:
				return
			visited[i][j] = True
			if A[i][j] == 0:
				return
			islands[label].append((i, j))
			dfs(i, j + 1)
			dfs(i, j - 1)
			dfs(i + 1, j)
			dfs(i - 1, j)
			found = True
		for i in range(len(A)):
			for j in range(len(A)):
				if not visited[i][j]:
					dfs(i, j)
					if found:
						label = 2
		(R, C) = (len(A), len(A[0]))

		def neighbors(r, c):
			for (nr, nc) in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
				if 0 <= nr < R and 0 <= nc < C:
					yield (nr, nc)
		(source, target) = (islands[1], islands[2])
		print((source, target))
		queue = collections.deque([(node, 0) for node in source])
		done = set(source)
		while queue:
			(node, d) = queue.popleft()
			if node in target:
				return d - 1
			for nei in neighbors(*node):
				if nei not in done:
					queue.append((nei, d + 1))
					done.add(nei)


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		m = len(A)
		n = len(A[0])
		visited = collections.deque()
		flag = False
		for i in range(m):
			for j in range(n):
				if A[i][j] == 1:
					A[i][j] = 2
					visited = self.search(A, i, j, visited)
					flag = True
					break
			if flag == True:
				break
		steps = 0
		vis = collections.deque(visited)
		while visited:
			size = len(visited)
			for i in range(size):
				(row, col) = visited.popleft()
				dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
				for d in dirs:
					newrow = row + d[0]
					newcol = col + d[1]
					if 0 <= newrow < len(A) and 0 <= newcol < len(A[0]) and (A[newrow][newcol] == 1):
						return steps
					elif 0 <= newrow < len(A) and 0 <= newcol < len(A[0]) and (A[newrow][newcol] == 0) and ((newrow, newcol) not in vis):
						A[newrow][newcol] = 2
						visited.append((newrow, newcol))
						vis.append((newrow, newcol))
			steps += 1
		return -1

	def search(self, A, i, j, visited):
		q = collections.deque()
		q.append((i, j))
		visited.append((i, j))
		while q:
			size = len(q)
			for i in range(size):
				(r, c) = q.popleft()
				dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
				for d in dirs:
					newr = r + d[0]
					newc = c + d[1]
					if 0 <= newr < len(A) and 0 <= newc < len(A[0]) and (A[newr][newc] == 1) and ((newr, newc) not in visited):
						A[newr][newc] = 2
						q.append((newr, newc))
						visited.append((newr, newc))
		return visited


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(found_y, found_x) = (None, None)
		for y in range(len(A)):
			found_one = False
			for x in range(len(A[0])):
				if A[y][x] == 1:
					(found_y, found_x) = (y, x)
					A = self.invertOnes(y, x, A)
					found_one = True
					break
			if found_one:
				break
		return self.BFS(found_y, found_x, A)

	def invertOnes(self, y, x, A):
		neighbors = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		stack = []
		stack.append((y, x))
		A[y][x] = -1
		while stack:
			(curr_y, curr_x) = stack.pop(0)
			for neighbor in neighbors:
				(new_y, new_x) = (curr_y + neighbor[0], curr_x + neighbor[1])
				if new_y >= 0 and new_y < len(A) and (new_x >= 0) and (new_x < len(A[0])) and (A[new_y][new_x] == 1):
					A[new_y][new_x] = -1
					stack.append((new_y, new_x))
		return A

	def BFS(self, y, x, A):
		visited = {}
		neighbors = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		stack = []
		stack.append((y, x, 0))
		visited[y, x] = 0
		min_dist = float('inf')
		while stack:
			(curr_y, curr_x, curr_dist) = stack.pop(0)
			if A[curr_y][curr_x] == 1:
				min_dist = min(min_dist, curr_dist - 1)
			for neighbor in neighbors:
				(new_y, new_x) = (curr_y + neighbor[0], curr_x + neighbor[1])
				if new_y >= 0 and new_y < len(A) and (new_x >= 0) and (new_x < len(A[0])):
					if A[new_y][new_x] == -1:
						new_dist = 0
					else:
						new_dist = curr_dist + 1
					if (new_y, new_x) not in visited:
						stack.append((new_y, new_x, new_dist))
						visited[new_y, new_x] = new_dist
					elif visited[new_y, new_x] > new_dist:
						visited[new_y, new_x] = new_dist
						stack.append((new_y, new_x, new_dist))
		return min_dist


from collections import deque

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def color(x, y):
			dfs = [(x, y)]
			while dfs:
				(a, b) = dfs.pop()
				A[a][b] = 2
				for (mx, my) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
					if 0 <= a + mx < len(A) and 0 <= b + my < len(A[0]):
						if A[a + mx][b + my] == 1:
							dfs.append((a + mx, b + my))

		def firstOne():
			for i in range(len(A)):
				for j in range(len(A[0])):
					if A[i][j]:
						color(i, j)
						return (i, j)
		point = firstOne()
		self.best = 1000

		def findClosest(point):
			visited = {}
			bfs = deque([(point, 0)])
			while bfs:
				(curr, dist) = bfs.popleft()
				if curr in visited:
					if visited[curr] <= dist:
						continue
				visited[curr] = dist
				for (x, y) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
					cx = curr[0] + x
					cy = curr[1] + y
					if 0 <= cx < len(A) and 0 <= cy < len(A[0]):
						if A[cx][cy] == 2:
							bfs.append(((cx, cy), 0))
						elif A[cx][cy] == 1:
							self.best = min(self.best, dist)
						else:
							bfs.append(((cx, cy), dist + 1))
		findClosest(point)
		return self.best


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		q = collections.deque()

		def find_first_island():
			for i in range(len(A)):
				for j in range(len(A[0])):
					if A[i][j] == 1:
						explore_island(i, j)
						return

		def explore_island(r, c):
			if not 0 <= r < len(A) or not 0 <= c < len(A[r]) or A[r][c] == -1:
				return
			if A[r][c] == 1:
				A[r][c] = -1
				explore_island(r + 1, c)
				explore_island(r - 1, c)
				explore_island(r, c + 1)
				explore_island(r, c - 1)
			elif A[r][c] == 0:
				q.append((r, c, 1))
		find_first_island()
		while q:
			(cur_r, cur_c, cur_l) = q.popleft()
			for (x, y) in ((cur_r + 1, cur_c), (cur_r - 1, cur_c), (cur_r, cur_c + 1), (cur_r, cur_c - 1)):
				if 0 <= x < len(A) and 0 <= y < len(A[0]):
					if A[x][y] == 1:
						return cur_l
					elif A[x][y] == 0:
						A[x][y] = -1
						q.append((x, y, cur_l + 1))


from typing import List
from collections import deque as queue
from functools import lru_cache

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		n = len(A)

		@lru_cache
		def neighbours(i, j):
			return [neighbour for neighbour in [(i - 1, j) if i > 0 else None, (i + 1, j) if i < n - 1 else None, (i, j - 1) if j > 0 else None, (i, j + 1) if j < n - 1 else None] if neighbour is not None]
		for i in range(n):
			for j in range(n):
				if A[i][j] == 1:
					first = (i, j)
		q = queue([first])
		visited = set()
		visited.add(first)
		while q:
			(i, j) = q.popleft()
			A[i][j] = 2
			for (ni, nj) in neighbours(i, j):
				if (ni, nj) not in visited and A[ni][nj] == 1:
					visited.add((ni, nj))
					q.append((ni, nj))
		min_distance = float('inf')
		for (li, lj) in visited:
			q = queue([(li, lj, 0)])
			water_visited = set()
			while q:
				(i, j, d) = q.popleft()
				for (ni, nj) in neighbours(i, j):
					if A[ni][nj] == 0 and (ni, nj) not in water_visited and (d + 1 < min_distance):
						water_visited.add((ni, nj))
						q.append((ni, nj, d + 1))
					elif A[ni][nj] == 1 and d < min_distance:
						min_distance = d
						if min_distance == 1:
							return 1
		return min_distance


import queue

def isOK(x, y, m, n):
	return x >= 0 and y >= 0 and (x < m) and (y < n)

def isOnEdge(A, x, y, m, n):
	xRows = [0, 0, -1, 1]
	yCols = [-1, 1, 0, 0]
	for i in range(4):
		new_x = x + xRows[i]
		new_y = y + yCols[i]
		if isOK(new_x, new_y, m, n) and A[new_x][new_y] == 0:
			return True
	return False
import queue

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		m = len(A)
		n = len(A[0])
		visited = [[False for _ in range(n)] for _ in range(m)]

		def dfs(start, island):
			(x, y) = start
			island.append(start)
			visited[x][y] = True
			xRows = [0, 0, -1, 1]
			yCols = [-1, 1, 0, 0]
			for i in range(4):
				new_x = x + xRows[i]
				new_y = y + yCols[i]
				if isOK(new_x, new_y, m, n) and (not visited[new_x][new_y]) and (A[new_x][new_y] == 1):
					dfs((new_x, new_y), island)
		islands = []
		for i in range(m):
			for j in range(n):
				if not visited[i][j] and A[i][j] == 1:
					island = []
					dfs((i, j), island)
					islands.append(island)
		island1 = islands[0]
		island2 = islands[1]
		visited = [[False for _ in range(n)] for _ in range(m)]

		def bfs(source_island, target_island, visited):
			q = queue.Queue()
			for start in source_island:
				(x, y) = start
				q.put((x, y, 0))
			cnt = 0
			while q.qsize() > 0:
				start = q.get()
				(x, y, w) = start
				xRows = [0, 0, -1, 1]
				yCols = [-1, 1, 0, 0]
				for i in range(4):
					new_x = x + xRows[i]
					new_y = y + yCols[i]
					if isOK(new_x, new_y, m, n) and (not visited[new_x][new_y]):
						if (new_x, new_y) in target_island:
							return w + 1
						visited[new_x][new_y] = True
						q.put((new_x, new_y, w + 1))
		return bfs(island1, island2, visited) - 1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		count = 0
		borders = collections.defaultdict(list)
		seen = set()
		(x, y) = ([1, -1, 0, 0], [0, 0, 1, -1])
		(m, n) = (len(A), len(A[0]))
		for i in range(m):
			for j in range(n):
				if A[i][j] == 1 and (i, j) not in seen:
					frontier = [(i, j)]
					island = {(i, j)}
					while frontier:
						cur = frontier.pop()
						bord = False
						for k in range(len(x)):
							(r, c) = (cur[0] + x[k], cur[1] + y[k])
							if 0 <= r < m and 0 <= c < n:
								if A[r][c] == 1 and (r, c) not in island:
									frontier.append((r, c))
									island.add((r, c))
								elif A[r][c] == 0:
									borders[count + 1].append(cur)
					count += 1
					seen.update(island)
				if count == 2:
					break
			if count == 2:
				break
		ans = float('inf')
		borders
		for (i, j) in borders[1]:
			for (x, y) in borders[2]:
				ans = min(ans, abs(i - x) + abs(j - y) - 1)
		return ans


def color(A, i, j, length):
	A[i][j] = 2
	if i > 0:
		if A[i - 1][j] == 1:
			color(A, i - 1, j, length)
	if j > 0:
		if A[i][j - 1] == 1:
			color(A, i, j - 1, length)
	if i < length - 1:
		if A[i + 1][j] == 1:
			color(A, i + 1, j, length)
	if j < length - 1:
		if A[i][j + 1] == 1:
			color(A, i, j + 1, length)

def expand(A, level, length):
	for i in range(length):
		for j in range(length):
			if A[i][j] == level:
				if i > 0:
					if A[i - 1][j] == 1:
						return level
					elif A[i - 1][j] == 0:
						A[i - 1][j] = level + 1
				if j > 0:
					if A[i][j - 1] == 1:
						return level
					elif A[i][j - 1] == 0:
						A[i][j - 1] = level + 1
				if i < length - 1:
					if A[i + 1][j] == 1:
						return level
					elif A[i + 1][j] == 0:
						A[i + 1][j] = level + 1
				if j < length - 1:
					if A[i][j + 1] == 1:
						return level
					elif A[i][j + 1] == 0:
						A[i][j + 1] = level + 1
	return 0

class Solution:

	def shortestBridge(self, A):
		length = len(A)
		found = 0
		for i in range(length):
			for j in range(length):
				if A[i][j]:
					found = 1
					color(A, i, j, length)
				if found == 1:
					break
			if found == 1:
				break
		level = 2
		found = 0
		while found == 0:
			found = expand(A, level, length)
			level += 1
		return found - 2


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		self.bfs = []
		flag = 1
		step = 0
		for i in range(len(A)):
			if flag:
				for j in range(len(A[0])):
					if A[i][j] == 1:
						self.dfs(A, i, j)
						flag = 0
						break
		while self.bfs:
			size = len(self.bfs)
			while size:
				(i, j) = self.bfs.pop(0)
				for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
					if 0 <= x < len(A) and 0 <= y < len(A[0]):
						if A[x][y] == 1:
							return step
						elif A[x][y] == 0:
							A[x][y] = -1
							self.bfs.append([x, y])
				size -= 1
			step += 1
		return step

	def dfs(self, A, i, j):
		if i >= len(A) or j >= len(A[0]) or i < 0 or (j < 0) or (A[i][j] != 1):
			return
		A[i][j] = -1
		self.bfs.append([i, j])
		self.dfs(A, i + 1, j)
		self.dfs(A, i - 1, j)
		self.dfs(A, i, j + 1)
		self.dfs(A, i, j - 1)


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		row_shifts = [-1, 0, 1, 0]
		col_shifts = [0, 1, 0, -1]

		def bfs_mark_first(row, col, mark):
			nonlocal A, row_shifts, col_shifts
			queue = [(row, col)]
			edges = []
			while len(queue) > 0:
				(curr_row, curr_col) = queue.pop(0)
				if A[curr_row][curr_col] == mark:
					continue
				A[curr_row][curr_col] = mark
				add_to_edges = False
				for (row_shift, col_shift) in zip(row_shifts, col_shifts):
					new_row = curr_row + row_shift
					new_col = curr_col + col_shift
					if 0 <= new_row < len(A) and 0 <= new_col < len(A[0]):
						if A[new_row][new_col] == 1:
							queue.append((new_row, new_col))
						else:
							add_to_edges = True
				if add_to_edges:
					edges.append((curr_row, curr_col))
			return edges
		terminate = False
		for row in range(len(A)):
			for col in range(len(A[0])):
				if A[row][col] == 1:
					edges = bfs_mark_first(row, col, -1)
					terminate = True
					break
			if terminate:
				break
		queue = edges
		while len(queue) > 0:
			(curr_row, curr_col) = queue.pop(0)
			for (row_shift, col_shift) in zip(row_shifts, col_shifts):
				new_row = curr_row + row_shift
				new_col = curr_col + col_shift
				if 0 <= new_row < len(A) and 0 <= new_col < len(A[0]):
					if A[new_row][new_col] == 0:
						A[new_row][new_col] = A[curr_row][curr_col] - 1
						queue.append((new_row, new_col))
					if A[new_row][new_col] == 1:
						return abs(A[curr_row][curr_col]) - 1
		return -1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		R = len(A)
		C = len(A[0])
		chk = [[0] * C for _ in range(R)]
		q = collections.deque()
		move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		flag = False
		for i in range(R):
			if flag:
				break
			for j in range(C):
				if A[i][j] == 1:
					self.dfs(i, j, A, chk, q)
					flag = True
					break
		res = 0
		while q:
			size = len(q)
			for _ in range(size):
				(i, j) = q.popleft()
				for m in move:
					(x, y) = (i + m[0], j + m[1])
					if 0 <= x < R and 0 <= y < C:
						chk[x][y] = 1
						if A[x][y] == 1:
							return res
						elif A[x][y] == 0:
							A[x][y] = 2
							q.append((x, y))
						else:
							continue
			res += 1
		return res

	def dfs(self, i, j, A, chk, q):
		if chk[i][j] == 1:
			return
		chk[i][j] = 1
		R = len(A)
		C = len(A[0])
		move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
		if A[i][j] == 1:
			q.append((i, j))
			A[i][j] = 2
			for m in move:
				x = i + m[0]
				y = j + m[1]
				if 0 <= x < R and 0 <= y < C:
					self.dfs(x, y, A, chk, q)


class Solution:

	def dfs(self, A, i, j):
		if 0 > i or i >= self.m or 0 > j or (j >= self.n) or (A[i][j] == 0) or (A[i][j] == 2):
			return
		A[i][j] = 2
		self.que.append([i, j])
		for (i0, j0) in self.offset:
			(ii, jj) = (i + i0, j + j0)
			self.dfs(A, ii, jj)

	def shortestBridge(self, A: List[List[int]]) -> int:
		self.offset = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		(self.m, self.n) = (len(A), len(A[0]))
		self.que = []
		ok = 0
		for i in range(self.m):
			for j in range(self.n):
				if A[i][j]:
					self.dfs(A, i, j)
					ok = 1
					break
			if ok:
				break
		rt = 0
		while len(self.que) > 0:
			qlen = len(self.que)
			for k in range(qlen):
				(i, j) = self.que.pop(0)
				for (i0, j0) in self.offset:
					(ii, jj) = (i + i0, j + j0)
					if 0 <= ii < self.m and 0 <= jj < self.n:
						if A[ii][jj] == 0:
							A[ii][jj] = 3
							self.que.append([ii, jj])
						elif A[ii][jj] == 1:
							return rt
			rt += 1
		return rt


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(x, y) = self.get_first(A)
		q = collections.deque()
		self.dfs(A, x, y, q)
		step = 0
		while q:
			new_q = collections.deque()
			size = len(q)
			for i in range(size):
				(x, y) = q.popleft()
				for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
					(nx, ny) = (x + d[0], y + d[1])
					if 0 <= nx < len(A) and 0 <= ny < len(A[0]):
						if A[nx][ny] == 1:
							return step
						elif A[nx][ny] == 0:
							new_q.append([nx, ny])
							A[nx][ny] = -1
			step += 1
			q = new_q
		return -1

	def get_first(self, A):
		for i in range(len(A)):
			for j in range(len(A[0])):
				if A[i][j] == 1:
					return (i, j)

	def dfs(self, A, x, y, q):
		A[x][y] = -1
		q.append([x, y])
		for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
			(nx, ny) = (x + d[0], y + d[1])
			if 0 <= nx < len(A) and 0 <= ny < len(A[0]) and (A[nx][ny] == 1):
				self.dfs(A, nx, ny, q)


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		originBridge = []

		def markBridge(cord):
			x = cord[1]
			y = cord[0]
			A[y][x] = 2
			originBridge.append(cord)
			if x < len(A[y]) - 1:
				if A[y][x + 1] == 1:
					markBridge((y, x + 1))
			if x > 0:
				if A[y][x - 1] == 1:
					markBridge((y, x - 1))
			if y < len(A) - 1:
				if A[y + 1][x] == 1:
					markBridge((y + 1, x))
			if y > 0:
				if A[y - 1][x] == 1:
					markBridge((y - 1, x))
		for y in range(len(A)):
			for x in range(len(A[y])):
				if A[y][x] == 1:
					markBridge((y, x))
					break
			if len(originBridge) > 0:
				break
		moves = 0
		bridgeList = set(originBridge)
		while len(originBridge) > 0:
			newMoves = []
			for b in originBridge:
				y = b[0]
				x = b[1]
				if x > 0:
					if (y, x - 1) not in bridgeList:
						if A[y][x - 1] == 1:
							return moves
						else:
							bridgeList.add((y, x - 1))
							newMoves.append((y, x - 1))
				if x < len(A[y]) - 1:
					if (y, x + 1) not in bridgeList:
						if A[y][x + 1] == 1:
							return moves
						else:
							bridgeList.add((y, x + 1))
							newMoves.append((y, x + 1))
				if y > 0:
					if (y - 1, x) not in bridgeList:
						if A[y - 1][x] == 1:
							return moves
						else:
							bridgeList.add((y - 1, x))
							newMoves.append((y - 1, x))
				if y < len(A) - 1:
					if (y + 1, x) not in bridgeList:
						if A[y + 1][x] == 1:
							return moves
						else:
							bridgeList.add((y + 1, x))
							newMoves.append((y + 1, x))
			originBridge = newMoves
			moves += 1
		return moves


from collections import deque
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		n = len(A)
		m = len(A[0])
		visited = [[False] * m for _ in range(n)]
		q = deque([])
		found = False
		for i in range(n):
			if found:
				break
			for j in range(m):
				if A[i][j] == 1:
					self.dfs(i, j, A, q, visited)
					found = True
					break
		step = 0
		while q:
			for _ in range(len(q)):
				(x, y) = q.popleft()
				for (dx, dy) in directions:
					(nx, ny) = (x + dx, y + dy)
					if not self.isValid(nx, ny, A) or visited[nx][ny]:
						continue
					if A[nx][ny] == 1:
						return step
					q.append((nx, ny))
					visited[nx][ny] = True
			step += 1
		return -1

	def dfs(self, i, j, A, q, visited):
		if not self.isValid(i, j, A) or visited[i][j] or A[i][j] == 0:
			return
		visited[i][j] = True
		q.append((i, j))
		for (dx, dy) in directions:
			(nx, ny) = (i + dx, j + dy)
			self.dfs(nx, ny, A, q, visited)

	def isValid(self, i, j, A):
		return i >= 0 and i < len(A) and (j >= 0) and (j < len(A[0]))


def color(A, i, j):
	if A[i][j] in (0, 2):
		return
	A[i][j] = 2
	if i > 0:
		if A[i - 1][j] == 1:
			color(A, i - 1, j)
	if j > 0:
		if A[i][j - 1] == 1:
			color(A, i, j - 1)
	if i < len(A) - 1:
		if A[i + 1][j] == 1:
			color(A, i + 1, j)
	if j < len(A) - 1:
		if A[i][j + 1] == 1:
			color(A, i, j + 1)

def expand(A):
	for l in range(2, len(A) ** 2):
		for i in range(len(A)):
			for j in range(len(A)):
				if A[i][j] == l:
					if i > 0:
						if A[i - 1][j] == 0:
							A[i - 1][j] = l + 1
						if A[i - 1][j] == 1:
							return l - 2
					if j > 0:
						if A[i][j - 1] == 0:
							A[i][j - 1] = l + 1
						if A[i][j - 1] == 1:
							return l - 2
					if i < len(A) - 1:
						if A[i + 1][j] == 0:
							A[i + 1][j] = l + 1
						if A[i + 1][j] == 1:
							return l - 2
					if j < len(A) - 1:
						if A[i][j + 1] == 0:
							A[i][j + 1] = l + 1
						if A[i][j + 1] == 1:
							return l - 2

class Solution:

	def shortestBridge(self, A):
		length = len(A)
		found = 0
		for i in range(length):
			for j in range(length):
				if A[i][j]:
					color(A, i, j)
					found = 1
					break
			if found == 1:
				break
		expansion = expand(A)
		return expansion


from collections import deque
Directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		queue = deque()
		found = False
		for i in range(len(A)):
			if found:
				break
			for j in range(len(A[0])):
				if A[i][j] == 1:
					visited = set()
					self.dfs(i, j, queue, A, visited)
					found = True
					break
		print(queue)
		step = 0
		while queue:
			for _ in range(len(queue)):
				(cur_x, cur_y) = queue.popleft()
				for (dx, dy) in Directions:
					(nx, ny) = (cur_x + dx, cur_y + dy)
					if not self.isValid(nx, ny, A) or (nx, ny) in visited:
						continue
					if A[nx][ny] == 1:
						return step
					queue.append((nx, ny))
					visited.add((nx, ny))
			step += 1
		return -1

	def dfs(self, i, j, queue, A, visited):
		if A[i][j] == 0:
			return
		queue.append((i, j))
		visited.add((i, j))
		for (dx, dy) in Directions:
			(nx, ny) = (i + dx, j + dy)
			if not self.isValid(nx, ny, A) or (nx, ny) in visited:
				continue
			self.dfs(nx, ny, queue, A, visited)

	def isValid(self, x, y, A):
		return x >= 0 and x < len(A) and (y >= 0) and (y < len(A[0]))


from random import randint
from collections import deque, Counter, defaultdict
from heapq import heappush, heappop, heapify
from scipy.special import comb, perm
from bisect import bisect, bisect_left, bisect_right

class Solution:

	def shortestBridge(self, A):
		(que, row, col, visited) = (deque(), len(A), len(A[0]), set())

		def dfs(i, j):
			if i < 0 or i > row - 1 or j < 0 or (j > col - 1) or ((i, j) in visited):
				return
			visited.add((i, j))
			if A[i][j] == 0:
				que.append((i, j))
				return
			for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
				dfs(ni, nj)
		found = False
		for i in range(row):
			for j in range(col):
				if A[i][j] == 1:
					dfs(i, j)
					found = True
					break
			if found:
				break
		cnt = 0
		while que:
			n = len(que)
			for _ in range(n):
				(i, j) = que.popleft()
				if A[i][j] == 1:
					return cnt
				for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
					if 0 <= ni < row and 0 <= nj < col and ((ni, nj) not in visited):
						que.append((ni, nj))
						visited.add((ni, nj))
			cnt += 1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(rows, cols) = (len(A), len(A[0]))
		starting_points = set()

		def traverse_island(r, c):
			A[r][c] = -1
			for (ar, ac) in [(r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)]:
				if 0 <= ar < rows and 0 <= ac < cols:
					if A[ar][ac] == 0:
						starting_points.add((ar, ac, 0))
					elif A[ar][ac] == 1:
						traverse_island(ar, ac)
		for r in range(rows):
			for c in range(cols):
				if A[r][c] == 1:
					traverse_island(r, c)
					break
			else:
				continue
			break
		q = deque(starting_points)
		while q:
			(r, c, dist) = q.popleft()
			for (ar, ac) in [(r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)]:
				if 0 <= ar < rows and 0 <= ac < cols and (A[ar][ac] != -1):
					if A[ar][ac] == 1:
						return dist + 1
					A[ar][ac] = -1
					q.append((ar, ac, dist + 1))
		return 0


from collections import deque

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		rows = len(A)
		cols = len(A[0]) if rows else 0
		if not rows or not cols:
			return -1
		self.queue = deque()
		self.visited = set()

		def floodFill(A, row, col, rows, cols):
			if not (0 <= row < rows and 0 <= col < cols):
				return
			if not A[row][col] or (row, col) in self.visited:
				return
			A[row][col] = 2
			self.queue.append((row, col, 0))
			self.visited.add((row, col))
			floodFill(A, row + 1, col, rows, cols)
			floodFill(A, row - 1, col, rows, cols)
			floodFill(A, row, col + 1, rows, cols)
			floodFill(A, row, col - 1, rows, cols)
		flood_fill = False
		for row in range(rows):
			for col in range(cols):
				if A[row][col] == 1:
					flood_fill = True
					floodFill(A, row, col, rows, cols)
					break
			if flood_fill:
				break
		directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
		while len(self.queue):
			(top_r, top_c, dist) = self.queue.popleft()
			for (d_r, d_c) in directions:
				n_r = top_r + d_r
				n_c = top_c + d_c
				if 0 <= n_r < rows and 0 <= n_c < cols and ((n_r, n_c) not in self.visited):
					if A[n_r][n_c] == 0:
						self.queue.append((n_r, n_c, dist + 1))
						self.visited.add((n_r, n_c))
					elif A[n_r][n_c] == 1:
						return dist
		return -1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def first():
			for i in range(len(A)):
				for j in range(len(A[0])):
					if A[i][j] == 1:
						return (i, j)

		def first_island(i, j):
			stack = [(i, j)]
			island = []
			dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
			while stack:
				(x, y) = stack.pop()
				A[x][y] = 2
				island.append((x, y, 0))
				for (dx, dy) in dirs:
					(tx, ty) = (x + dx, y + dy)
					if len(A) > tx >= 0 and len(A[0]) > ty >= 0 and (A[tx][ty] == 1):
						stack.append((tx, ty))
			return island

		def bfs(queue):
			queue = collections.deque(queue)
			dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
			while queue:
				length = len(queue)
				for _ in range(length):
					(x, y, level) = queue.popleft()
					for (dx, dy) in dirs:
						(tx, ty) = (x + dx, y + dy)
						if len(A) > tx >= 0 and len(A[0]) > ty >= 0:
							if A[tx][ty] == 1:
								return level
							elif not A[tx][ty]:
								A[tx][ty] = -1
								queue.append((tx, ty, level + 1))
		return bfs(first_island(*first()))


import heapq
import sys
sys.setrecursionlimit(10 ** 8)

class First:
	val = True

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(h, w) = (len(A), len(A[0]))
		direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
		First.val = True
		visited = [[0 for i in range(w)] for i in range(h)]

		def dfs(y, x, color):
			visited[y][x] = 1
			A[y][x] = color
			for (dy, dx) in direction:
				(ny, nx) = (y + dy, x + dx)
				if ny < 0 or ny >= h or nx < 0 or (nx >= w):
					continue
				if visited[ny][nx] or A[ny][nx] == 0:
					continue
				dfs(ny, nx, color)
		for i in range(h):
			for j in range(w):
				if visited[i][j]:
					continue
				if A[i][j]:
					if First.val:
						First.val = False
						dfs(i, j, 1)
					else:
						dfs(i, j, 2)
						break

		def bfs(i, j, start):
			q = [[0, i, j]]
			answer = 0
			while q:
				(step, y, x) = heapq.heappop(q)
				if A[y][x] and A[y][x] != start:
					return step
				for (dy, dx) in direction:
					(ny, nx) = (y + dy, x + dx)
					if ny < 0 or ny >= h or nx < 0 or (nx >= w):
						continue
					if visited[ny][nx] == 2:
						continue
					visited[ny][nx] = 2
					if A[ny][nx]:
						heapq.heappush(q, [step, ny, nx])
					else:
						heapq.heappush(q, [step + 1, ny, nx])
		result = 0
		for i in range(h):
			for j in range(w):
				if visited[i][j] == 2:
					continue
				if A[i][j]:
					start = A[i][j]
					result = bfs(i, j, start)
					break
			if result:
				break
		return result


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def isvalid(row, col):
			return 0 <= row < len(A) and 0 <= col < len(A[0])

		def dfs(row, col):
			if not isvalid(row, col) or A[row][col] != 1:
				return
			A[row][col] = 2
			for (i, j) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
				new_row = row + i
				new_col = col + j
				dfs(new_row, new_col)
			return
		found = False
		for row in range(len(A)):
			for col in range(len(A[0])):
				if A[row][col] == 1:
					dfs(row, col)
					found = True
					break
			if found:
				break
		twos = []
		for row in range(len(A)):
			for col in range(len(A[0])):
				if A[row][col] == 2:
					twos.append((row, col))
		steps = 0
		while twos:
			next_ = []
			steps += 1
			for point in twos:
				(row, col) = point
				for (i, j) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
					new_row = row + i
					new_col = col + j
					if isvalid(new_row, new_col) and A[new_row][new_col] == 0:
						A[new_row][new_col] = -1
						next_.append((new_row, new_col))
					elif isvalid(new_row, new_col) and A[new_row][new_col] == 1:
						return steps - 1
			twos = next_
		return -1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		q = collections.deque()

		def ExploreIslands(x, y):
			if not 0 <= x < len(A) or not 0 <= y < len(A[0]) or A[x][y] == -1:
				return
			if A[x][y] == 1:
				A[x][y] = -1
				ExploreIslands(x, y + 1)
				ExploreIslands(x, y - 1)
				ExploreIslands(x + 1, y)
				ExploreIslands(x - 1, y)
			else:
				q.appendleft((x, y, 1))

		def FindFirstIsland():
			for (i, row) in enumerate(A):
				for (j, val) in enumerate(row):
					if val == 1:
						ExploreIslands(i, j)
						return
		FindFirstIsland()
		while True:
			(x, y, distance) = q.popleft()
			for (new_x, new_y) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
				if 0 <= new_x < len(A) and 0 <= new_y < len(A[0]):
					if A[new_x][new_y] == 1:
						return distance
					elif A[new_x][new_y] == 0:
						A[new_x][new_y] = -1
						q.append((new_x, new_y, distance + 1))


import collections

class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		visited = set()

		def do_dfs(A, i, j, visited, seen):
			visited.add((i, j))
			seen.add((i, j))
			for (x, y) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
				if 0 <= x < len(A) and 0 <= y < len(A[0]) and A[x][y] and ((x, y) not in visited):
					do_dfs(A, x, y, visited, seen)
		comp = []
		for i in range(len(A)):
			for j in range(len(A[0])):
				if A[i][j] == 1 and (i, j) not in visited:
					seen = set()
					do_dfs(A, i, j, visited, seen)
					comp.append(seen)
		(s, t) = (comp[0], comp[1])
		queue = collections.deque([(node, 0) for node in s])
		done = s
		while queue:
			(node, d) = queue.popleft()
			if node in t:
				return d - 1
			for n in [(node[0] + 1, node[1]), (node[0] - 1, node[1]), (node[0], node[1] + 1), (node[0], node[1] - 1)]:
				if 0 <= n[0] < len(A) and 0 <= n[1] < len(A[0]) and (n not in done):
					queue.append((n, d + 1))
					done.add(n)


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		m = len(A)
		n = len(A[0])
		found = 0
		queue = []

		def dfs(a, b):
			queue.append((a, b))
			A[a][b] = -1
			for (x, y) in ((a + 1, b), (a - 1, b), (a, b + 1), (a, b - 1)):
				if 0 <= x < m and 0 <= y < n and (A[x][y] == 1):
					dfs(x, y)
		for i in range(m):
			if found:
				break
			for j in range(n):
				if A[i][j] == 1:
					found = 1
					dfs(i, j)
					break
		step = 0
		while queue:
			new_queue = []
			for (x, y) in queue:
				for (_x, _y) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
					if 0 <= _x < m and 0 <= _y < n:
						if A[_x][_y] == 1:
							return step
						elif not A[_x][_y]:
							A[_x][_y] = -1
							new_queue.append((_x, _y))
			step += 1
			queue = new_queue
		return -1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def neighbors(u, v):
			for (du, dv) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
				(nu, nv) = (u + du, v + dv)
				if 0 <= nu < m and 0 <= nv < n:
					yield (nu, nv)

		def components():

			def dfs(u, v, acc):
				acc.add((u, v))
				visited.add((u, v))
				for (nu, nv) in neighbors(u, v):
					if (nu, nv) not in visited and A[nu][nv] == 1:
						dfs(nu, nv, acc)
			res = []
			visited = set()
			for u in range(m):
				for v in range(n):
					if A[u][v] == 1 and (u, v) not in visited:
						res.append(set())
						dfs(u, v, res[-1])
			return res

		def bfs(ps, pt):
			q = deque()
			visited = set()
			for p in ps:
				q.append(p)
				visited.add(p)
			distance = 0
			while q:
				qsize = len(q)
				for i in range(qsize):
					(u, v) = q.popleft()
					for (nu, nv) in neighbors(u, v):
						if (nu, nv) in pt:
							return distance
						if (nu, nv) not in visited:
							q.append((nu, nv))
							visited.add((nu, nv))
				distance += 1
			return 0
		m = len(A)
		n = len(A[0])
		(source, target) = components()
		return bfs(source, target)


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(R, C) = (len(A), len(A[0]))
		done = set()

		def dfs(x, y, seen, R, C):
			if A[x][y] == 0:
				return
			seen.add((x, y))
			for (nr, nc) in ((x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)):
				if 0 <= nr < R and 0 <= nc < C and (A[nr][nc] == 1) and ((nr, nc) not in seen) and ((nr, nc) not in done):
					dfs(nr, nc, seen, R, C)
		islands = []
		for (r, row) in enumerate(A):
			for (c, col) in enumerate(row):
				if col and (r, c) not in done:
					seen = set()
					dfs(r, c, seen, R, C)
					islands.append(seen)
					done |= seen
		(first, second) = islands
		q = list(first)
		count = 0
		seen = set()
		while q:
			temp = []
			for (x, y) in q:
				for (nx, ny) in ((x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)):
					if 0 <= nx < R and 0 <= ny < C and ((nx, ny) not in first) and ((nx, ny) not in seen):
						if (nx, ny) in second:
							return count
						temp.append((nx, ny))
						seen.add((nx, ny))
			count += 1
			q = temp[:]
		return 0


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(R, C) = (len(A), len(A[0]))

		def inside(i, j):
			return 0 <= i < R and 0 <= j < C

		def dfs_paint_2(i, j):
			A[i][j] = 2
			for (ii, jj) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if inside(ii, jj) and A[ii][jj] == 1:
					dfs_paint_2(ii, jj)

		def neighbor_is_1(i, j):
			for (ii, jj) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if inside(ii, jj) and A[ii][jj] == 1:
					return True
			return False

		def paint_neighbor(i, j, color):
			for (ii, jj) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if inside(ii, jj) and A[ii][jj] == 0:
					A[ii][jj] = color
		for (i, row) in enumerate(A):
			for (j, ele) in enumerate(row):
				if ele == 1:
					dfs_paint_2(i, j)
					break
			else:
				continue
			break
		for color in range(2, max(R, C) + 2):
			for (i, row) in enumerate(A):
				for (j, ele) in enumerate(row):
					if ele == color:
						if neighbor_is_1(i, j):
							return color - 2
						paint_neighbor(i, j, color + 1)


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		q = collections.deque()

		def explore_island(r, c):
			if not 0 <= r < len(A) or not 0 <= c < len(A[r]) or A[r][c] == -1:
				return
			if A[r][c] == 1:
				A[r][c] = -1
				explore_island(r + 1, c)
				explore_island(r - 1, c)
				explore_island(r, c + 1)
				explore_island(r, c - 1)
			elif A[r][c] == 0:
				q.append((r, c, 1))

		def find_first_island():
			for (r, row) in enumerate(A):
				for (c, v) in enumerate(row):
					if v == 1:
						explore_island(r, c)
						return
		find_first_island()
		while q:
			(cur_r, cur_c, cur_l) = q.popleft()
			for (x, y) in ((cur_r + 1, cur_c), (cur_r - 1, cur_c), (cur_r, cur_c + 1), (cur_r, cur_c - 1)):
				if 0 <= x < len(A) and 0 <= y < len(A[x]):
					if A[x][y] == 1:
						return cur_l
					elif A[x][y] == 0:
						A[x][y] = -1
						q.append((x, y, cur_l + 1))
					continue


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		m = len(A)
		n = len(A[0])

		def get_poss(i, j, val=1):
			poss = [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]
			poss = [(x, y) for (x, y) in poss if x >= 0 and x < m and (y >= 0) and (y < n) and (A[x][y] == val)]
			return poss

		def expand(i, j):
			A[i][j] = '#'
			poss = get_poss(i, j)
			for (x, y) in poss:
				expand(x, y)
		found_first = False
		boundaries = []
		for i in range(m):
			for j in range(n):
				if A[i][j] == 1:
					if not found_first:
						found_first = True
						expand(i, j)
					else:
						boundaries.append((i, j))

		def bfs(boundaries):
			recorder = set(boundaries)
			depth = 0
			roots = boundaries
			while roots:
				next_level = []
				for (x, y) in roots:
					poss1 = get_poss(x, y, '#')
					if poss1:
						return depth
					poss = get_poss(x, y, 0)
					for pos in poss:
						if pos not in recorder:
							recorder.add(pos)
							next_level.append(pos)
				depth += 1
				roots = next_level
		return bfs(boundaries)


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		island_one = set()

		def dfs(r, c):
			if (r, c) in island_one:
				return
			island_one.add((r, c))
			for (r1, c1) in {(r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)}:
				if 0 <= r1 < len(A) and 0 <= c1 < len(A[0]) and ((r1, c1) not in island_one) and (A[r1][c1] == 1):
					dfs(r1, c1)
		f = False
		for i in range(len(A)):
			for j in range(len(A[0])):
				if A[i][j] == 1:
					dfs(i, j)
					f = True
					break
			if f:
				break

		def bfs():
			q = collections.deque([(r, c, 0) for (r, c) in list(island_one)])
			seen = set()
			while q:
				(r, c, level) = q.popleft()
				if A[r][c] == 1 and (r, c) not in island_one:
					return level - 1
				for (r1, c1) in {(r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)}:
					if 0 <= r1 < len(A) and 0 <= c1 < len(A[0]) and (A[r1][c1] not in island_one) and ((r1, c1) not in seen):
						q.append((r1, c1, level + 1))
						seen.add((r1, c1))
		return bfs()


import heapq

class Solution:
	directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]

	def shortestBridge(self, mat: List[List[int]]) -> int:
		row = None
		col = None
		found = False
		for i in range(len(mat)):
			if found:
				break
			for j in range(len(mat[i])):
				if mat[i][j]:
					row = i
					col = j
					Solution.paint_one_island(mat, row, col, mat[row][col] + 1)
					found = True
					break
		target_dest = 1
		return Solution.minimum_expand(mat, row, col, target_dest)

	@staticmethod
	def mark_next(mat, row, col, val, target_dest):
		for i in range(len(Solution.directions)):
			new_row = row + Solution.directions[i][0]
			new_col = col + Solution.directions[i][1]
			if new_row < 0 or new_row >= len(mat) or new_col < 0 or (new_col >= len(mat[0])):
				continue
			if mat[new_row][new_col] == target_dest:
				return True
			if not mat[new_row][new_col]:
				mat[new_row][new_col] = val + 1
		return False

	@staticmethod
	def minimum_expand(mat, row, col, target_dest):
		st_val = mat[row][col]
		for val in range(st_val, len(mat) * len(mat[0])):
			for row in range(len(mat)):
				for col in range(len(mat[row])):
					is_reached = False
					if mat[row][col] == val:
						is_reached = Solution.mark_next(mat, row, col, val, target_dest)
					if is_reached:
						return val - st_val
		return -1

	@staticmethod
	def paint_one_island(mat, row, col, val):
		if row < 0 or row >= len(mat) or col < 0 or (col >= len(mat[0])):
			return
		if mat[row][col] == val or not mat[row][col]:
			return
		mat[row][col] = val
		for i in range(len(Solution.directions)):
			Solution.paint_one_island(mat, row + Solution.directions[i][0], col + Solution.directions[i][1], val)


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(M, N) = (len(A), len(A[0]))

		def dfs(i, j):
			A[i][j] = 2
			for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if 0 <= x < M and 0 <= y < N and (A[x][y] == 1):
					dfs(x, y)
			return
		flag = 0
		for i in range(M):
			for j in range(N):
				if A[i][j] == 1:
					flag = 1
					break
			if flag:
				break
		dfs(i, j)
		q = collections.deque([(0, i, j) for i in range(M) for j in range(N) if A[i][j] == 1])
		seen = set([(i, j) for i in range(M) for j in range(N) if A[i][j] == 1])
		while q:
			(step, i, j) = q.popleft()
			if A[i][j] == 2:
				return step - 1
			for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if 0 <= x < M and 0 <= y < N and ((x, y) not in seen) and (A[x][y] in [0, 2]):
					seen.add((x, y))
					q.append((step + 1, x, y))


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(m, n) = (len(A), len(A[0]))
		self.first = []

		def dfs(i, j, m, n):
			if 0 <= i < m and 0 <= j < n and (A[i][j] == 1):
				A[i][j] = 2
				self.first.append((i, j))
				for (r, c) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
					dfs(r, c, m, n)
		for i in range(m):
			for j in range(n):
				if A[i][j] == 1:
					dfs(i, j, m, n)
					break
			if A[i][j] == 2:
				break
		res = m * n
		while self.first:
			(i, j) = self.first.pop(0)
			for (r, c) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if 0 <= r < m and 0 <= c < n:
					if A[r][c] == 0:
						A[r][c] = A[i][j] + 1
						self.first.append((r, c))
					if A[r][c] == 1:
						res = min(res, A[i][j] - 2)
						A[i][j] == -1
						break
			if A[i][j] == -1:
				break
		return res


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		n = len(A)
		zeros = set()

		def dfs(i, j):
			A[i][j] = 2
			for (di, dj) in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
				(ii, jj) = (i + di, j + dj)
				if 0 <= ii < n and 0 <= jj < n:
					if A[ii][jj] == 1:
						dfs(ii, jj)
					elif A[ii][jj] == 0:
						zeros.add((ii, jj))
		for i in range(n):
			for j in range(n):
				if A[i][j] == 1:
					dfs(i, j)
					break
			else:
				continue
			break
		result = 2 * n
		q = collections.deque(zeros)
		visited = {(i, j)}
		steps = 1
		while q:
			for _ in range(len(q)):
				(i, j) = q.popleft()
				for (di, dj) in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
					(ii, jj) = (i + di, j + dj)
					if 0 <= ii < n and 0 <= jj < n:
						if A[ii][jj] == 0 and (ii, jj) not in visited:
							visited.add((ii, jj))
							q.append((ii, jj))
						if A[ii][jj] == 1:
							result = min(result, steps)
			steps += 1
		return result


class Solution:

	def transform_island(self, A, i, j, queue, visited):
		if i < 0 or i >= len(A) or j < 0 or (j >= len(A[i])) or ((i, j) in visited):
			return
		if A[i][j] == 0:
			return
		A[i][j] = float('inf')
		queue.append((0, i, j))
		visited.add((i, j))
		self.transform_island(A, i + 1, j, queue, visited)
		self.transform_island(A, i, j + 1, queue, visited)
		self.transform_island(A, i - 1, j, queue, visited)
		self.transform_island(A, i, j - 1, queue, visited)

	def shortestBridge(self, A: List[List[int]]) -> int:
		queue = collections.deque([])
		visited = set()
		for i in range(len(A)):
			should_break = False
			for j in range(len(A[i])):
				if A[i][j] == 1:
					self.transform_island(A, i, j, queue, set())
					should_break = True
					break
			if should_break:
				break
		while len(queue) > 0:
			(prev_val, i, j) = queue.popleft()
			next_val = prev_val - 1
			print(('q', i, j, next_val))
			if A[i][j] == 1:
				return -prev_val - 1
			if i > 0 and A[i - 1][j] >= 0 and ((i - 1, j) not in visited):
				visited.add((i - 1, j))
				queue.append((next_val, i - 1, j))
			if i < len(A) - 1 and A[i + 1][j] >= 0 and ((i + 1, j) not in visited):
				visited.add((i + 1, j))
				queue.append((next_val, i + 1, j))
			if j > 0 and A[i][j - 1] >= 0 and ((i, j - 1) not in visited):
				visited.add((i, j - 1))
				queue.append((next_val, i, j - 1))
			if j < len(A[0]) - 1 and A[i][j + 1] >= 0 and ((i, j + 1) not in visited):
				visited.add((i, j + 1))
				queue.append((next_val, i, j + 1))


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		m = len(A)
		n = len(A[0])
		q = collections.deque([])
		for i in range(m):
			for j in range(n):
				if A[i][j] == 1:
					q.append((i, j))
					newq = collections.deque([(i, j)])
					break
			else:
				continue
			break
		while q:
			(x, y) = q.popleft()
			A[x][y] = 2
			for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
				(nx, ny) = (x + dx, y + dy)
				if 0 <= nx < m and 0 <= ny < n and (A[nx][ny] == 1):
					A[nx][ny] = 2
					newq.append((nx, ny))
					q.append((nx, ny))
		steps = 0
		while newq:
			newsize = len(newq)
			for _ in range(newsize):
				(x, y) = newq.popleft()
				for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
					(nx, ny) = (x + dx, y + dy)
					if nx < 0 or nx >= m or ny < 0 or (ny >= m) or (A[nx][ny] == 2):
						continue
					if A[nx][ny] == 1:
						return steps
					elif A[nx][ny] == 0:
						A[nx][ny] = 2
						newq.append((nx, ny))
			steps += 1
		return -1


from collections import deque

class Solution:

	def findNeighbors(self, root, A):
		(i, j) = root
		neighbors = []
		if i > 0:
			neighbors.append((i - 1, j))
		if j > 0:
			neighbors.append((i, j - 1))
		if i < len(A) - 1:
			neighbors.append((i + 1, j))
		if j < len(A[0]) - 1:
			neighbors.append((i, j + 1))
		return neighbors

	def findIsland(self, root, A):
		queue = [root]
		visited = set()
		while queue:
			pick = queue.pop()
			if pick in visited:
				continue
			visited.add(pick)
			neighbors = self.findNeighbors(pick, A)
			for neighbor in neighbors:
				if A[neighbor[0]][neighbor[1]] == 1:
					queue.append(neighbor)
		return visited

	def shortestBridge(self, A: List[List[int]]) -> int:
		root = None
		for i in range(len(A)):
			for j in range(len(A[0])):
				if A[i][j] == 1:
					root = (i, j)
		queue = deque(self.findIsland(root, A))
		level = 0
		visited = self.findIsland(root, A)
		while queue:
			print((level, queue, visited))
			for _ in range(len(queue)):
				pick = queue.popleft()
				for neighbor in self.findNeighbors(pick, A):
					if neighbor in visited:
						continue
					visited.add(neighbor)
					if A[neighbor[0]][neighbor[1]] == 1:
						print(neighbor)
						return level
					queue.append(neighbor)
			level += 1
		return level


class Solution:

	def shortestBridge(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0
		nrow = len(grid)
		ncol = len(grid[0])
		q = deque()

		def explore_island(grid, i, j):
			if i < 0 or i >= nrow or j < 0 or (j >= ncol) or (grid[i][j] != 1):
				return
			grid[i][j] = 2
			q.append((i, j, 0))
			for (ni, nj) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				explore_island(grid, ni, nj)

		def get_coordinates(grid):
			for i in range(nrow):
				for j in range(ncol):
					if grid[i][j] == 1:
						explore_island(grid, i, j)
						return
			return
		get_coordinates(grid)
		while q:
			(i, j, dist) = q.popleft()
			for (ni, nj) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if ni >= 0 and ni < nrow and (nj >= 0) and (nj < ncol) and (grid[ni][nj] != 2):
					if grid[ni][nj] == 1:
						return dist
					elif grid[ni][nj] == 0:
						grid[ni][nj] = 2
						q.append((ni, nj, dist + 1))


class Solution:

	def __init__(self):
		self.map = None
		(self.w, self.h) = (0, 0)

	def get_neighbors(self, r, c):
		nei = []
		for rc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
			if 0 <= rc[0] < self.h and 0 <= rc[1] < self.w:
				nei.append(rc)
		return nei

	def find_island(self):
		done = set()
		islands = []
		for r in range(len(self.map)):
			for c in range(len(self.map[0])):
				if self.map[r][c] and (r, c) not in done:
					stack = [(r, c)]
					seen = {(r, c)}
					while stack:
						cell = stack.pop(0)
						neighbors = self.get_neighbors(cell[0], cell[1])
						for nei in neighbors:
							if self.map[nei[0]][nei[1]] and nei not in seen:
								stack.append(nei)
								seen.add(nei)
					islands.append(seen)
					done |= seen
		return islands

	def shortestBridge(self, A: List[List[int]]) -> int:
		self.map = A
		(self.w, self.h) = (len(A), len(A[0]))
		(source, target) = self.find_island()
		queue = [(node, 0) for node in source]
		while queue:
			(node, d) = queue.pop(0)
			if node in target:
				return d - 1
			neighbors = self.get_neighbors(node[0], node[1])
			for nei in neighbors:
				if nei not in source:
					queue.append((nei, d + 1))
					source.add(nei)


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		row_len = len(A)
		col_len = len(A[0])

		def neighbour(r, c):
			for (i, j) in [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]:
				if 0 <= i < row_len and 0 <= j < col_len:
					yield (i, j)

		def helper(A, r, c, queue):
			if not (0 <= r < row_len and 0 <= c < col_len) or A[r][c] == 0 or A[r][c] == 2:
				return
			A[r][c] = 2
			queue.append((r, c))
			for (i, j) in neighbour(r, c):
				helper(A, i, j, queue)
		start_r = -1
		start_c = -1
		for r in range(row_len):
			for c in range(col_len):
				if A[r][c] == 1:
					start_r = r
					start_c = c
					break
		queue = deque()
		helper(A, start_r, start_c, queue)
		step = 0
		while queue:
			size = len(queue)
			for i in range(size):
				(r, c) = queue.popleft()
				for (i, j) in neighbour(r, c):
					if A[i][j] == 1:
						return step
					if A[i][j] == 0:
						A[i][j] = 2
						queue.append((i, j))
			step += 1


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(N, M) = (len(A), len(A[0]))

		def labelIsland(i, j):
			stack = [(i, j)]
			visited = {(i, j)}
			while stack:
				(x, y) = stack.pop()
				A[x][y] = 2
				for (nx, ny) in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
					if 0 <= nx < N and 0 <= ny < M and ((nx, ny) not in visited):
						if A[nx][ny] == 1:
							visited.add((nx, ny))
							stack.append((nx, ny))
			return visited

		def bfs(source) -> int:
			queue = collections.deque([(0, x[0], x[1]) for x in source])
			visited = source
			ans = math.inf
			while queue:
				(dist, x, y) = queue.popleft()
				for (nx, ny) in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
					if 0 <= nx < N and 0 <= ny < M and ((nx, ny) not in visited):
						if A[nx][ny] == 1:
							return dist
						else:
							visited.add((nx, ny))
							queue.append((dist + 1, nx, ny))
			return ans
		ans = math.inf
		for i in range(N):
			for j in range(M):
				if A[i][j] == 1:
					source = labelIsland(i, j)
					return bfs(source)


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		n = len(A)

		def getFirst():
			for (i, row) in enumerate(A):
				for (j, point) in enumerate(row):
					if point == 1:
						return (i, j)
		islandA = []
		boundaries = set()
		stack = [getFirst()]
		while len(stack) > 0:
			(i, j) = stack.pop()
			A[i][j] = -1
			islandA.append((i, j))
			isBound = False
			for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
				if 0 <= x < n and 0 <= y < n:
					if A[x][y] == 0:
						boundaries.add((i, j))
					elif A[x][y] == 1:
						stack.append((x, y))
		step = 0
		while boundaries:
			new = []
			for (i, j) in boundaries:
				for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
					if 0 <= x < n and 0 <= y < n:
						if A[x][y] == 1:
							return step
						elif not A[x][y]:
							A[x][y] = -1
							new.append((x, y))
			step += 1
			boundaries = new


class Solution:

	def mark_island(self, A, row, column, marker, border_coordinates):
		if 0 <= row < len(A) and 0 <= column < len(A[0]) and (A[row][column] != marker):
			if A[row][column] == 0:
				return True
			else:
				A[row][column] = marker
				rets = [self.mark_island(A, row + 1, column, marker, border_coordinates), self.mark_island(A, row - 1, column, marker, border_coordinates), self.mark_island(A, row, column + 1, marker, border_coordinates), self.mark_island(A, row, column - 1, marker, border_coordinates)]
				if True in rets:
					border_coordinates.append((row, column))
		return False

	def shortestBridge(self, A: List[List[int]]) -> int:
		border_coordinates = [[], []]
		marker = 2
		smallest_distance = len(A) * len(A[0])
		for row in range(len(A)):
			for column in range(len(A[0])):
				if A[row][column] == 1:
					self.mark_island(A, row, column, marker, border_coordinates[marker - 2])
					marker += 1
		for coordinates1 in border_coordinates[0]:
			for coordinates2 in border_coordinates[1]:
				distance = abs(coordinates1[0] - coordinates2[0]) + abs(coordinates1[1] - coordinates2[1]) - 1
				if distance < smallest_distance:
					smallest_distance = distance
		return smallest_distance


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		m = len(A)
		n = len(A[0])

		def get_neighbors(i, j):
			dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
			ans = []
			for (dx, dy) in dirs:
				new_i = i + dx
				new_j = j + dy
				if 0 <= new_i < m and 0 <= new_j < n:
					ans.append((new_i, new_j))
			return ans

		def dfs_visit(i, j, visited):
			if A[i][j] != 1:
				return
			if (i, j) in visited:
				return
			visited.add((i, j))
			for neighbor in get_neighbors(i, j):
				dfs_visit(neighbor[0], neighbor[1], visited)
			return
		source_nodes = set()
		break_flag = False
		for i in range(m):
			if break_flag:
				break
			for j in range(n):
				if A[i][j] == 1:
					dfs_visit(i, j, source_nodes)
					break_flag = True
					break
		q = []
		for (i, j) in source_nodes:
			q.append(((i, j), 0))
		visited = set()
		while len(q):
			(curr_node, curr_dist) = q.pop(0)
			for neighbor in get_neighbors(curr_node[0], curr_node[1]):
				if neighbor in source_nodes:
					continue
				if neighbor in visited:
					continue
				if A[neighbor[0]][neighbor[1]] == 1:
					return curr_dist
				visited.add(neighbor)
				q.append((neighbor, curr_dist + 1))
		return


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def findIslandA(i, j):
			A[i][j] = -1
			islandA.append((i, j))
			for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
				if 0 <= x < n and 0 <= y < n and (A[x][y] == 1):
					findIslandA(x, y)

		def first():
			for i in range(n):
				for j in range(n):
					if A[i][j]:
						return (i, j)
		(n, step, islandA) = (len(A), 0, [])
		findIslandA(*first())
		while islandA:
			boundaries = []
			for (i, j) in islandA:
				for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
					if 0 <= x < n and 0 <= y < n:
						if A[x][y] == 1:
							return step
						elif A[x][y] == 0:
							A[x][y] = -1
							boundaries.append((x, y))
			step += 1
			islandA = boundaries


class Solution:

	def shortestBridge(self, grid: List[List[int]]) -> int:

		def dfs(curr_i, curr_j, outliners):
			visited.add((curr_i, curr_j))
			for (delta_i, delta_j) in [(1, 0), (0, 1), (0, -1), (-1, 0)]:
				(next_i, next_j) = (curr_i + delta_i, curr_j + delta_j)
				if 0 <= next_i < m and 0 <= next_j < n:
					if grid[next_i][next_j] == 0:
						outliners.add((next_i, next_j))
					elif grid[next_i][next_j] == 1:
						if (next_i, next_j) not in visited:
							dfs(next_i, next_j, outliners)
		(m, n) = (len(grid), len(grid[0]))
		visited = set()
		(outliners_1, outliners_2) = (set(), set())
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1 and (i, j) not in visited:
					if len(outliners_1) == 0:
						dfs(i, j, outliners_1)
					else:
						dfs(i, j, outliners_2)
		min_dist = m + n
		for (i, j) in outliners_1:
			for (p, q) in outliners_2:
				min_dist = min(min_dist, abs(i - p) + abs(j - q) + 1)
		return min_dist


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:

		def dfs(i, j, A, visited):
			m = len(A)
			n = len(A[0])
			if 0 <= i < m and 0 <= j < n and (A[i][j] == 1) and ((i, j) not in visited):
				visited.add((i, j))
				dfs(i + 1, j, A, visited)
				dfs(i - 1, j, A, visited)
				dfs(i, j + 1, A, visited)
				dfs(i, j - 1, A, visited)
		m = len(A)
		n = len(A[0])
		find = False
		visited = set()
		for i in range(m):
			for j in range(n):
				if A[i][j] == 1:
					find = True
					dfs(i, j, A, visited)
					break
			if find:
				break
		visited_zero = set()
		queue = []
		for (i, j) in visited:
			for (_i, _j) in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
				if 0 <= i + _i < m and 0 <= j + _j < n and ((i + _i, j + _j) not in visited):
					assert A[i + _i][j + _j] == 0
					visited_zero.add((i + _i, j + _j))
					queue.append((i + _i, j + _j, 1))
		res = 0
		find = False
		while not find:
			(i, j, dist) = queue.pop(0)
			for (_i, _j) in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
				if 0 <= i + _i < m and 0 <= j + _j < n and ((i + _i, j + _j) not in visited_zero) and ((i + _i, j + _j) not in visited):
					if A[i + _i][j + _j] == 0:
						visited_zero.add((i + _i, j + _j))
						queue.append((i + _i, j + _j, dist + 1))
					else:
						find = True
						res = dist
		return res


class Solution:

	def shortestBridge(self, A: List[List[int]]) -> int:
		(i1, i2) = self.find_islands(A)
		for (x, y, n) in self.enlarge(i1):
			if (x, y) in i2:
				return n

	def find_islands(self, A: List[List[int]]) -> List[Set[Tuple[int, int]]]:
		visited = set()
		islands = []
		for (x, ys) in enumerate(A):
			for (y, c) in enumerate(ys):
				if (x, y) not in visited and c == 1:
					to_visit = [(x, y)]
					island = set()
					while to_visit:
						(cx, cy) = to_visit.pop(0)
						if (cx, cy) in visited:
							continue
						visited.add((cx, cy))
						island.add((cx, cy))
						for (ax, ay) in self.adjacent((cx, cy)):
							if ax >= 0 and ay >= 0 and (ax < len(A)) and (ay < len(A[ax])) and (A[ax][ay] == 1):
								to_visit.append((ax, ay))
					islands.append(island)
		return islands

	def enlarge(self, island: Set[Tuple[int, int]]) -> Generator[Tuple[int, int, int], None, None]:
		visited = set()
		to_visit = []
		for (x, y) in island:
			visited.add((x, y))
			for (ax, ay) in self.adjacent((x, y)):
				visited.add((x, y))
				if (ax, ay) not in island:
					to_visit.append((ax, ay, 0))
		while to_visit:
			(x, y, n) = to_visit.pop(0)
			if (x, y) in visited:
				continue
			visited.add((x, y))
			for (ax, ay) in self.adjacent((x, y)):
				if (ax, ay) in visited:
					continue
				to_visit.append((ax, ay, n + 1))
			yield (x, y, n)

	def adjacent(self, cell: Tuple[int, int]) -> List[Tuple[int, int]]:
		return [(cell[0] + x, cell[1] + y) for (x, y) in [(-1, 0), (1, 0), (0, -1), (0, 1)]]