Aterp is the head nurse at a city hospital. City hospital contains R*C number of wards and the structure of a hospital is in the form of a 2-D matrix.
Given a matrix of dimension R*C where each cell in the matrix can have values 0, 1, or 2 which has the following meaning:
0: Empty ward
1: Cells have uninfected patients
2: Cells have infected patients
An infected patient at ward [i,j] can infect other uninfected patient at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right) in unit time. Help Aterp determine the minimum units of time after which there won't remain any uninfected patient i.e all patients would be infected. If all patients are not infected after infinite units of time then simply return -1.
 
Example 1:
Input:
3 5
2 1 0 2 1
1 0 1 2 1
1 0 0 2 1 
Output:
2
Explanation:
Patients at positions {0,0}, {0, 3}, {1, 3}
and {2, 3} will infect patient at {0, 1}, 
{1, 0},{0, 4}, {1, 2}, {1, 4}, {2, 4} during 1st 
unit time. And, during 2nd unit time, patient at 
{1, 0} will get infected and will infect patient 
at {2, 0}. Hence, total 2 unit of time is
required to infect all patients.
Example 2:
Input:
3 5
2 1 0 2 1
0 0 1 2 1
1 0 0 2 1
Output:
-1
Explanation:
All patients will not be infected.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function helpaterp() which takes a 2-D Matrix hospital as input parameter and returns the minimum units of time in which all patients will be infected or -1 if it is impossible.
Constraints:
1 ≤ R,C ≤ 1000
0 ≤ mat[i][j] ≤ 2

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Graph algorithms

Graph traversal

Starter code: #User function Template for python3



class Solution:

    def helpaterp(self, hospital):

        # code here

        

Solutions:
from collections import deque

class Solution:

	def helpaterp(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		q = deque()
		ans = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					q.append((i, j, 0))
		while q:
			(r, c, t) = q.popleft()
			ans = t
			l = [[-1, 0], [1, 0], [0, 1], [0, -1]]
			for (i, j) in l:
				(nr, nc) = (r + i, c + j)
				if nr < n and nr >= 0 and (nc < m) and (nc >= 0) and (grid[nr][nc] == 1):
					grid[nr][nc] = 2
					q.append((nr, nc, t + 1))
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					return -1
		return ans


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		q = deque()
		n = len(hospital)
		m = len(hospital[0])
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 2:
					q.append((i, j, 0))
		ans = 0
		dx = [-1, 0, 0, 1]
		dy = [0, -1, 1, 0]
		while len(q) > 0:
			k = len(q)
			for i in range(k):
				(x, y, d) = q.popleft()
				ans = d
				for j in range(4):
					nx = x + dx[j]
					ny = y + dy[j]
					if nx >= 0 and nx < n and (ny >= 0) and (ny < m) and (hospital[nx][ny] == 1):
						hospital[nx][ny] = 2
						q.append((nx, ny, d + 1))
		for line in hospital:
			if 1 in line:
				return -1
		return ans


class Solution:

	def helpaterp(self, x):
		(m, n) = (len(x), len(x[0]))
		q = []
		for i in range(m):
			for j in range(n):
				if x[i][j] == 2:
					q.append((i, j, 0))
		ma = 0
		while q:
			(i, j, k) = q.pop(0)
			ma = max(ma, k)
			for (d, e) in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
				if 0 <= d < m and 0 <= e < n and (x[d][e] == 1):
					q.append((d, e, k + 1))
					x[d][e] = 2
		return ma if all((all((x[i][j] != 1 for j in range(n))) for i in range(m))) else -1


from collections import deque

class Solution:

	def helpaterp(self, grid):
		m = len(grid)
		n = len(grid[0])
		fresh = 0
		q = deque()
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 2:
					q.append((i, j, 0))
				if grid[i][j] == 1:
					fresh += 1
		minute = 0
		while q:
			(r, c, minute) = q.popleft()
			lst = [(r - 1, c), (r + 1, c), (r, c + 1), (r, c - 1)]
			for (row, col) in lst:
				if 0 <= row < m and 0 <= col < n and (grid[row][col] == 1):
					grid[row][col] = 2
					fresh -= 1
					q.append((row, col, minute + 1))
		if fresh > 0:
			return -1
		else:
			return minute


class Solution:

	def isValid(self, i, j, m, n):
		if i >= 0 and j >= 0 and (i < m) and (j < n):
			return True
		else:
			return False

	def helpaterp(self, hospital):
		(m, n) = (len(hospital), len(hospital[0]))
		q = []
		ni = set()
		for i in range(m):
			for j in range(n):
				if hospital[i][j] == 1:
					ni.add((i, j))
				if hospital[i][j] == 2:
					q.append([i, j])
		ans = 0
		while q and ni:
			l = len(q)
			for i in range(l):
				tuple = q.pop(0)
				if self.isValid(tuple[0] + 1, tuple[1], m, n) and (tuple[0] + 1, tuple[1]) in ni:
					ni.remove((tuple[0] + 1, tuple[1]))
					q.append([tuple[0] + 1, tuple[1]])
				if self.isValid(tuple[0] - 1, tuple[1], m, n) and (tuple[0] - 1, tuple[1]) in ni:
					ni.remove((tuple[0] - 1, tuple[1]))
					q.append([tuple[0] - 1, tuple[1]])
				if self.isValid(tuple[0], tuple[1] + 1, m, n) and (tuple[0], tuple[1] + 1) in ni:
					ni.remove((tuple[0], tuple[1] + 1))
					q.append([tuple[0], tuple[1] + 1])
				if self.isValid(tuple[0], tuple[1] - 1, m, n) and (tuple[0], tuple[1] - 1) in ni:
					ni.remove((tuple[0], tuple[1] - 1))
					q.append([tuple[0], tuple[1] - 1])
			ans += 1
		return -1 if len(ni) != 0 else ans


from collections import deque

class Solution:

	def helpaterp(self, hos):
		n = len(hos)
		m = len(hos[0])
		assert 1 <= n <= 1000 and 1 <= m <= 1000
		mat = [[0] * m for i in range(n)]
		q = deque()
		for i in range(n):
			for j in range(m):
				assert hos[i][j] == 0 or hos[i][j] == 1 or hos[i][j] == 2
				if hos[i][j] == 2:
					q.append([i, j])
				elif hos[i][j] == 1:
					mat[i][j] = 10 ** 5
				else:
					mat[i][j] = -1
		dx = [1, 0, -1, 0]
		dy = [0, 1, 0, -1]
		while len(q) != 0:
			li = q.popleft()
			x = li[0]
			y = li[1]
			for i in range(4):
				nx = x + dx[i]
				ny = y + dy[i]
				if nx >= 0 and nx < n and (ny >= 0) and (ny < m) and (mat[nx][ny] != -1) and (mat[nx][ny] > mat[x][y]):
					mat[nx][ny] = 1 + mat[x][y]
					q.append([nx, ny])
		ans = 0
		for i in range(n):
			for j in range(m):
				ans = max(ans, mat[i][j])
		if ans == 10 ** 5:
			return -1
		elif ans == -1:
			return 0
		else:
			return ans


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		q = deque()
		dx = [0, 0, -1, 1]
		dy = [-1, 1, 0, 0]
		arr = [[] for i in range(len(hospital))]
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				arr[i].append
				if hospital[i][j] == 1:
					arr[i].append(-1)
				elif hospital[i][j] == 2:
					arr[i].append(0)
					q.append((i, j))
				else:
					arr[i].append(-2)
		while len(q):
			size = len(q)
			for i in range(size):
				u = q.popleft()
				for j in range(4):
					x = dx[j] + u[0]
					y = dy[j] + u[1]
					if x >= 0 and y >= 0 and (x < len(hospital)) and (y < len(hospital[0])) and (arr[x][y] == -1):
						q.append((x, y))
						arr[x][y] = arr[u[0]][u[1]] + 1
		ans = 0
		for i in range(len(arr)):
			for j in range(len(arr[0])):
				if arr[i][j] == -1:
					return -1
				ans = max(ans, arr[i][j])
		return ans


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		n = len(hospital)
		m = len(hospital[0])
		d = [[1000000000.0 for j in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 2:
					d[i][j] = 0
				if hospital[i][j] == 0:
					d[i][j] = -1
		for i1 in range(n):
			for j1 in range(m):
				if hospital[i1][j1] == 2:
					q = deque()
					q.append((i1, j1))
					while len(q) > 0:
						u = q.popleft()
						i = u[0]
						j = u[1]
						if i - 1 >= 0 and hospital[i - 1][j] == 1 and (d[i - 1][j] > d[i][j] + 1):
							d[i - 1][j] = d[i][j] + 1
							q.append((i - 1, j))
						if i + 1 < n and hospital[i + 1][j] == 1 and (d[i + 1][j] > d[i][j] + 1):
							d[i + 1][j] = d[i][j] + 1
							q.append((i + 1, j))
						if j - 1 >= 0 and hospital[i][j - 1] == 1 and (d[i][j - 1] > d[i][j] + 1):
							d[i][j - 1] = d[i][j] + 1
							q.append((i, j - 1))
						if j + 1 < m and hospital[i][j + 1] == 1 and (d[i][j + 1] > d[i][j] + 1):
							d[i][j + 1] = d[i][j] + 1
							q.append((i, j + 1))
		time = 0
		for i in range(n):
			for j in range(m):
				if d[i][j] > time:
					time = d[i][j]
		if time == 1000000000.0:
			return -1
		return time


class Solution:

	def is_valid(self, newx, newy, mat, row, col):
		if newx < 0 or newx >= row or newy < 0 or (newy >= col) or (mat[newx][newy] != 1):
			return False
		return True

	def helpaterp(self, mat):
		row = len(mat)
		col = len(mat[0])
		q = list()
		for i in range(row):
			for j in range(col):
				if mat[i][j] == 2:
					q.append([i, j])
		if len(q) == 0:
			return -1
		directions = [[-1, 0], [0, -1], [0, 1], [1, 0]]
		time = 0
		while len(q) > 0:
			size = len(q)
			flag = False
			while size > 0:
				(cur_x, cur_y) = q.pop(0)
				for x in directions:
					newx = cur_x + x[0]
					newy = cur_y + x[1]
					if self.is_valid(newx, newy, mat, row, col):
						q.append([newx, newy])
						mat[newx][newy] = 2
						flag = True
				size -= 1
			if flag:
				time += 1
		for i in range(row):
			for j in range(col):
				if mat[i][j] == 1:
					return -1
		return time


from collections import deque

class Solution:

	def helpaterp(self, grid):
		dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
		que = deque()
		(n, m) = (len(grid), len(grid[0]))
		cnt = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					que.append((0, i, j))
				if grid[i][j] == 1:
					cnt += 1
		while que:
			(dis, i, j) = que.popleft()
			for (delRow, delCol) in dirc:
				nr = delRow + i
				nc = delCol + j
				if nr >= 0 and nr < n and (nc >= 0) and (nc < m) and (grid[nr][nc] == 1):
					grid[nr][nc] = 2
					que.append((dis + 1, nr, nc))
					cnt -= 1
		if cnt == 0:
			return dis
		return -1


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		n = len(hospital)
		m = len(hospital[0])
		infected = deque()
		maxi = 0
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 2:
					infected.append((i, j, 0))
		while infected:
			(i, j, time) = infected.popleft()
			if hospital[i][j] == 0:
				continue
			hospital[i][j] = 0
			maxi = max(maxi, time)
			if i > 0:
				infected.append((i - 1, j, time + 1))
			if i < n - 1:
				infected.append((i + 1, j, time + 1))
			if j > 0:
				infected.append((i, j - 1, time + 1))
			if j < m - 1:
				infected.append((i, j + 1, time + 1))
		for row in hospital:
			if 1 in row:
				return -1
		return maxi


from collections import deque

class Solution:

	def isValid(self, x, y, r, c):
		return 0 <= x < r and 0 <= y < c

	def helpaterp(self, hospital):
		r = len(hospital)
		c = len(hospital[0])
		moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		visited = [[False for _ in range(c)] for _ in range(r)]
		q = deque()
		for i in range(r):
			for j in range(c):
				if hospital[i][j] == 2:
					visited[i][j] = True
					q.append((i, j))
		ans = 0
		while len(q):
			qsize = len(q)
			infected = False
			for i in range(qsize):
				(x, y) = q.popleft()
				for move in moves:
					nx = x + move[0]
					ny = y + move[1]
					if not self.isValid(nx, ny, r, c):
						continue
					if visited[nx][ny]:
						continue
					if hospital[nx][ny] == 1:
						if not infected:
							ans += 1
							infected = True
						hospital[nx][ny] = 2
						visited[nx][ny] = True
						q.append((nx, ny))
		for i in range(r):
			for j in range(c):
				if hospital[i][j] == 1:
					return -1
		return ans


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		n = len(hospital)
		m = len(hospital[0])
		visit = [[0] * m for _ in range(n)]
		q = deque()
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 2:
					q.append([i, j, 0])
					visit[i][j] = 1
		t1 = 0
		while q:
			t = q.popleft()
			row = t[0]
			col = t[1]
			time = t[2]
			t1 = max(t1, time)
			for i in range(-1, 2):
				nrow = row + i
				if nrow >= 0 and nrow < n and (visit[nrow][col] == 0) and (hospital[nrow][col] == 1):
					hospital[nrow][col] = 2
					visit[nrow][col] = 1
					q.append([nrow, col, time + 1])
			for i in range(-1, 2):
				ncol = col + i
				if ncol >= 0 and ncol < m and (visit[row][ncol] == 0) and (hospital[row][ncol] == 1):
					hospital[row][ncol] = 2
					visit[row][ncol] = 1
					q.append([row, ncol, time + 1])
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 1:
					return -1
		return t1


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		que = deque()
		visited = [[0] * len(hospital[0]) for i in range(len(hospital))]
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] == 2:
					que.append((i, j, 0))
					visited[i][j] = True
		x = [-1, 1, 0, 0]
		y = [0, 0, -1, 1]
		m = 0
		while que:
			v = que.popleft()
			for i in range(4):
				x1 = x[i] + v[0]
				y1 = y[i] + v[1]
				if x1 >= 0 and y1 >= 0 and (x1 < len(hospital)) and (y1 < len(hospital[0])) and (not visited[x1][y1]) and hospital[x1][y1]:
					que.append((x1, y1, v[2] + 1))
					visited[x1][y1] = True
					m = max(m, v[2] + 1)
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] != 0 and (not visited[i][j]):
					return -1
		return m


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		(R, C) = (len(hospital), len(hospital[0]))
		que = deque()
		for r in range(R):
			for c in range(C):
				if hospital[r][c] == 2:
					que.append((r, c))
		level = 0
		while que:
			for _ in range(len(que)):
				(ci, cj) = que.popleft()
				for (ni, nj) in self.get_nbrs(ci, cj, R, C):
					if hospital[ni][nj] == 1:
						hospital[ni][nj] = 2
						que.append((ni, nj))
			level += 1
		for r in range(R):
			for c in range(C):
				if hospital[r][c] == 1:
					return -1
		return level - 1

	def get_nbrs(self, pi, pj, m, n):
		res = []
		for (di, dj) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
			ni = pi + di
			nj = pj + dj
			if 0 <= ni < m and 0 <= nj < n:
				res.append((ni, nj))
		return res


class Solution:

	def helpaterp(self, hospital):
		uninfected = 0
		(m, n) = (len(hospital), len(hospital[0]))
		q = []
		for i in range(m):
			for j in range(n):
				if hospital[i][j] == 1:
					uninfected += 1
				elif hospital[i][j] == 2:
					q.append([i, j])
		ans = 0
		dir = [[0, -1], [-1, 0], [1, 0], [0, 1]]

		def validCorr(i, j):
			return i >= 0 and i < m and (j >= 0) and (j < n)
		while uninfected > 0 and len(q) > 0:
			for _ in range(len(q)):
				(r, c) = q.pop(0)
				for (dr, dc) in dir:
					(row, col) = (r + dr, c + dc)
					if validCorr(row, col) and hospital[row][col] == 1:
						hospital[row][col] = 2
						uninfected -= 1
						q.append([row, col])
			ans += 1
		return ans if uninfected == 0 else -1


from copy import deepcopy

class Solution:

	def helpaterp(self, hospital):
		(self.row, self.col) = (len(hospital), len(hospital[0]))
		(self.next, self.patient) = ([[0, -1], [-1, 0], [0, 1], [1, 0]], [0, 0, 0])
		self.hospital = deepcopy(hospital)
		for i in hospital:
			for j in i:
				self.patient[j] += 1
		if self.patient[1] == 0:
			return 0
		if self.patient[2] == 0:
			if self.patient[1] > 0:
				return -1
			return 0
		time = 0
		while self.patient[2] > 0:
			for i in range(self.row):
				for j in range(self.col):
					if hospital[i][j] == 2:
						self.helper(i, j)
			(hospital, time) = (deepcopy(self.hospital), time + 1)
			if self.patient[1] == 0:
				return time
		if self.patient[1]:
			return -1
		return time

	def helper(self, x, y):
		(self.hospital[x][y], self.patient[2]) = (0, self.patient[2] - 1)
		for (x1, y1) in self.next:
			(x2, y2) = (x + x1, y + y1)
			if -1 < x2 < self.row and -1 < y2 < self.col and (self.hospital[x2][y2] == 1):
				(self.hospital[x2][y2], self.patient[2], self.patient[1]) = (2, self.patient[2] + 1, self.patient[1] - 1)


from collections import deque

def isInside(i, j, n, m):
	if i >= 0 and i < n and (j >= 0) and (j < m):
		return True
	return False

def getAvailableNeighbors(i, j, n, m, grid, ct, val):
	dx = [-1, 1, 0, 0]
	dy = [0, 0, 1, -1]
	avail = deque([])
	for w in range(len(dy)):
		x = i + dx[w]
		y = j + dy[w]
		if isInside(x, y, n, m) and grid[x][y] == val:
			avail.append((x, y, ct))
	return avail

class Solution:

	def helpaterp(self, grid):
		n = len(grid)
		m = len(grid[0])
		rotted = deque()
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					rotted.append((i, j, 0))
		ct = 0
		while rotted:
			r = rotted.popleft()
			if r[2] > ct:
				ct = r[2]
			neighs = getAvailableNeighbors(r[0], r[1], n, m, grid, r[2] + 1, 1)
			for neigh in neighs:
				rotted.append(neigh)
				grid[neigh[0]][neigh[1]] = 2
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					return -1
		return ct


class Solution:

	def helpaterp(self, hospital):
		directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		queue = []
		total_uninfected_patients = 0
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] == 2:
					queue.append([i, j])
				elif hospital[i][j] == 1:
					total_uninfected_patients += 1
		if not total_uninfected_patients:
			return 0
		time_taken = 0
		while queue and total_uninfected_patients:
			time_taken += 1
			for _ in range(len(queue)):
				(row, col) = queue.pop(0)
				for direction in directions:
					next_row = row + direction[0]
					next_col = col + direction[1]
					if not self.is_valid(next_row, next_col, hospital):
						continue
					total_uninfected_patients -= 1
					hospital[next_row][next_col] = 2
					queue.append([next_row, next_col])
		return time_taken if not total_uninfected_patients else -1

	def is_valid(self, row, col, hospital):
		if row >= 0 and col >= 0 and (row < len(hospital)) and (col < len(hospital[0])) and (hospital[row][col] == 1):
			return True
		return False


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		n = len(hospital)
		m = len(hospital[0])
		q = deque()
		directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		one = 0
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 2:
					q.append((i, j, 0))
				elif hospital[i][j] == 1:
					one += 1
		while q:
			(r, c, dis) = q.popleft()
			for (i, j) in directions:
				row = i + r
				col = j + c
				if row in range(n) and col in range(m):
					if hospital[row][col] == 1:
						q.append((row, col, dis + 1))
						one -= 1
						hospital[row][col] = 2
		if one > 0:
			return -1
		return dis


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		n = len(hospital)
		m = len(hospital[0])
		timer = 0
		visited = [[0 for i in range(m)] for j in range(n)]
		queue = deque()
		for i in range(0, n):
			for j in range(0, m):
				if hospital[i][j] == 2:
					queue.append([[i, j], 0])
		delrow = [-1, 0, 1, 0]
		delcol = [0, 1, 0, -1]
		while queue:
			ele = queue.popleft()
			row = ele[0][0]
			col = ele[0][1]
			time = ele[1]
			timer = max(timer, time)
			for i in range(0, 4):
				nrow = row + delrow[i]
				ncol = col + delcol[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (visited[nrow][ncol] == 0) and (hospital[nrow][ncol] == 1):
					visited[nrow][ncol] = 1
					queue.append([[nrow, ncol], time + 1])
		for i in range(0, n):
			for j in range(0, m):
				if visited[i][j] == 0 and hospital[i][j] == 1:
					return -1
		return timer


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		step = 0
		t = 0
		n = len(hospital)
		m = len(hospital[0])
		q = deque()
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 2:
					q.append((i, j))
				elif hospital[i][j] == 1:
					t += 1
		if t == 0:
			return step
		while q:
			tt = len(q)
			for _ in range(tt):
				(r, c) = q.popleft()
				for (u, v) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
					nr = r + u
					nc = v + c
					if nr > -1 and nr < n and (nc > -1) and (nc < m) and (hospital[nr][nc] == 1):
						hospital[nr][nc] = 2
						q.append((nr, nc))
						t -= 1
			step += 1
		if t == 0:
			return step - 1
		return -1


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		row = len(hospital)
		col = len(hospital[0])
		st = deque()
		for i in range(row):
			for j in range(col):
				if hospital[i][j] == 2:
					st.append((i, j))
		dist = -1
		while st:
			l = len(st)
			mod = 0
			for i in range(l):
				(x, y) = st.popleft()
				if hospital[x][y] == 2 and dist >= 0:
					continue
				hospital[x][y] = 2
				mod += 1
				for (x1, y1) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
					if x1 >= 0 and x1 < row and (y1 < col) and (y1 >= 0):
						if hospital[x1][y1] == 1:
							st.append((x1, y1))
			if mod > 0:
				dist += 1
		for i in range(row):
			for j in range(col):
				if hospital[i][j] == 1:
					return -1
		return dist


class Solution:

	def helpaterp(self, hospital):
		x = len(hospital)
		y = len(hospital[0])
		q = []
		for i in range(x):
			for j in range(y):
				if hospital[i][j] == 2:
					hospital[i][j] = 0
					q.append(((i, j), 0))
		time = 0
		while q:
			levelLen = len(q)
			for l in range(levelLen):
				(c, t) = q.pop(0)
				(row, col) = (c[0], c[1])
				time = max(time, t)
				if row - 1 >= 0:
					if hospital[row - 1][col] == 1:
						hospital[row - 1][col] = 0
						q.append(((row - 1, col), t + 1))
				if row + 1 < x:
					if hospital[row + 1][col] == 1:
						hospital[row + 1][col] = 0
						q.append(((row + 1, col), t + 1))
				if col - 1 >= 0:
					if hospital[row][col - 1] == 1:
						hospital[row][col - 1] = 0
						q.append(((row, col - 1), t + 1))
				if col + 1 < y:
					if hospital[row][col + 1] == 1:
						hospital[row][col + 1] = 0
						q.append(((row, col + 1), t + 1))
		for a in range(len(hospital)):
			for b in range(len(hospital[0])):
				if hospital[a][b] == 1:
					return -1
		return time


from queue import Queue

class Solution:

	def helpaterp(self, hospital):
		N = len(hospital)
		M = len(hospital[0])
		visited = [[False for _ in range(M)] for _ in range(N)]
		dxx = [0, 0, -1, +1]
		dyy = [-1, +1, 0, 0]

		def is_Valid(i, j):
			return 0 <= i < N and 0 <= j < M and (not visited[i][j]) and (hospital[i][j] == 1)
		unaffected_person = 0
		q = Queue()
		for i in range(N):
			for j in range(M):
				if hospital[i][j] == 2:
					q.put(((i, j), 0))
					visited[i][j] = True
				elif hospital[i][j] == 1:
					unaffected_person += 1
		timme = -1
		while not q.empty():
			((i, j), timme) = q.get()
			for (dx, dy) in zip(dxx, dyy):
				if is_Valid(i + dx, j + dy):
					q.put(((i + dx, j + dy), timme + 1))
					visited[i + dx][j + dy] = True
					unaffected_person -= 1
		if unaffected_person != 0:
			return -1
		return timme


class Solution:

	def helpaterp(self, board):
		n = len(board)
		m = len(board[0])
		q = []
		s = {}
		for i in range(n):
			for j in range(m):
				if board[i][j] == 2:
					q.append([0, i, j])
				if board[i][j] == 1:
					s[i, j] = 1
		c = 0
		r = [-1, 0, 1, 0]
		cols = [0, 1, 0, -1]
		while c != len(q):
			d = q[c][0]
			row = q[c][1]
			col = q[c][2]
			for i in range(4):
				newr = row + r[i]
				newc = col + cols[i]
				if newc >= 0 and newr >= 0 and (newr < n) and (newc < m) and (board[newr][newc] == 1):
					board[newr][newc] = 2
					del s[newr, newc]
					q.append([d + 1, newr, newc])
			c += 1
		if len(s) != 0:
			return -1
		return d


class Solution:

	def helpaterp(self, hospital):
		vis = [[0 for _ in range(len(hospital[0]))] for __ in range(len(hospital))]
		ans = 0
		count = 0
		q = []
		for i in range(0, len(hospital)):
			for j in range(0, len(hospital[0])):
				if hospital[i][j] == 2:
					q.append([[i, j], 0])
		x = self.bfs(q, hospital, vis)
		for i in range(0, len(hospital)):
			for j in range(0, len(hospital[0])):
				if hospital[i][j] == 1:
					return -1
		return x

	def bfs(self, q, h, v):
		while q:
			x = q.pop(0)
			row = x[0][0]
			col = x[0][1]
			level = x[1]
			de = [[row + 1, col], [row, col + 1], [row - 1, col], [row, col - 1]]
			v[row][col] = 1
			for i in de:
				r = i[0]
				c = i[1]
				if r >= 0 and c >= 0 and (c < len(h[0])) and (r < len(h)) and (v[r][c] != 1) and (h[r][c] == 1):
					v[r][c] = 1
					h[r][c] = 2
					q.append([[r, c], level + 1])
		return level


class Solution:

	def helpaterp(self, hospital):
		n = len(hospital)
		m = len(hospital[0])
		vis = [[False for _ in range(m)] for _ in range(n)]
		ans = 0
		q = []
		dx = [-1, 0, 1, 0]
		dy = [0, 1, 0, -1]
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 2:
					q.append([i, j])
					vis[i][j] = True
		while q:
			size = len(q)
			flag = False
			while size > 0:
				t = q.pop(0)
				x = t[0]
				y = t[1]
				for i in range(4):
					nx = x + dx[i]
					ny = y + dy[i]
					if self.isInside(nx, ny, n, m, vis) and hospital[nx][ny] == 1:
						flag = True
						hospital[nx][ny] = 2
						vis[nx][ny] = True
						q.append([nx, ny])
				size -= 1
			if flag == True:
				ans += 1
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 1:
					return -1
		return ans

	def isInside(self, nx, ny, n, m, vis):
		if nx < 0 or nx >= n or ny < 0 or (ny >= m) or (vis[nx][ny] == True):
			return False
		else:
			return True


class Solution:

	def helpaterp(self, hospital):
		arr = hospital
		n = len(arr)
		m = len(arr[0])
		l1 = []
		for i in range(n):
			for j in range(m):
				if arr[i][j] == 2:
					l1.append([i, j])
		l2 = []
		time = 0
		dr = [1, -1, 0, 0]
		dc = [0, 0, 1, -1]
		while len(l1) != 0:
			for i in l1:
				(cr, cc) = i
				for i in range(4):
					nr = cr + dr[i]
					nc = cc + dc[i]
					if nr >= 0 and nr < n and (nc >= 0) and (nc < m):
						if arr[nr][nc] == 1:
							arr[nr][nc] = 2
							l2.append([nr, nc])
			l1 = l2[:]
			l2 = []
			time += 1
		for i in range(n):
			for j in range(m):
				if arr[i][j] == 1:
					return -1
		return time - 1


MAX = float('inf')

def isvalid(A, nx, ny):
	N = len(A)
	M = len(A[0])
	if nx >= 0 and nx < N and (ny >= 0) and (ny < M) and (A[nx][ny] == 1):
		return 1
	return 0

class Solution:

	def helpaterp(self, A):
		N = len(A)
		M = len(A[0])
		dp = [[MAX for _ in range(M)] for _ in range(N)]
		q = []
		c = 0
		for i in range(N):
			for j in range(M):
				if A[i][j] == 2:
					q.append([i, j])
					dp[i][j] = 0
				elif A[i][j] == 1:
					c += 1
		dx = [0, 0, 1, -1]
		dy = [1, -1, 0, 0]
		ans = -MAX
		while q:
			(x, y) = q.pop(0)
			for i in range(4):
				nx = x + dx[i]
				ny = y + dy[i]
				if isvalid(A, nx, ny) and dp[nx][ny] == MAX:
					dp[nx][ny] = 1 + dp[x][y]
					q.append([nx, ny])
					ans = max(ans, dp[nx][ny])
					c -= 1
		if c != 0:
			return -1
		return ans


class Solution:

	def helpaterp(self, hospital):
		m = len(hospital)
		n = len(hospital[0])
		visited = [[False for i in range(n)] for j in range(m)]
		q = []
		for i in range(m):
			for j in range(n):
				if hospital[i][j] == 2:
					q.append((i, j))
					visited[i][j] = True
		res = -1
		while q:
			l = len(q)
			res += 1
			while l:
				l -= 1
				(r, c) = q.pop(0)
				for (i, j) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
					nr = r + i
					nc = c + j
					if self.isValid(nr, nc, m, n) and (not visited[nr][nc]) and (hospital[nr][nc] == 1):
						q.append((nr, nc))
						visited[nr][nc] = True
						hospital[nr][nc] = 2
		for i in range(m):
			for j in range(n):
				if hospital[i][j] == 1:
					return -1
		return res

	def isValid(self, i, j, m, n):
		if i < 0 or j < 0 or i >= m or (j >= n):
			return False
		return True


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		rows = len(hospital)
		cols = len(hospital[0])
		uninfected = 0
		q = deque()
		for i in range(rows):
			for j in range(cols):
				if hospital[i][j] == 1:
					uninfected += 1
				if hospital[i][j] == 2:
					q.append((i, j))
		timer = 0
		directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
		while q and uninfected > 0:
			size = len(q)
			for i in range(size):
				pos = q.popleft()
				for direction in directions:
					r = direction[0] + pos[0]
					c = direction[1] + pos[1]
					if r < 0 or c < 0 or r >= rows or (c >= cols) or (hospital[r][c] != 1):
						continue
					uninfected -= 1
					hospital[r][c] = 2
					q.append((r, c))
			timer += 1
		return timer if uninfected == 0 else -1


class Solution:

	def helpaterp(self, hospital):
		row = len(hospital)
		col = len(hospital[0])
		q = []
		count = 0
		mins = 0
		cnt = 0
		for i in range(row):
			for j in range(col):
				if hospital[i][j] != 0:
					count += 1
				if hospital[i][j] == 2:
					q.append([i, j])
		dx = [0, 0, -1, 1]
		dy = [1, -1, 0, 0]
		while q:
			k = len(q)
			cnt += k
			while k:
				cur = q.pop(0)
				x = cur[0]
				y = cur[1]
				k -= 1
				for i in range(4):
					nx = x + dx[i]
					ny = dy[i] + y
					if nx < 0 or nx >= row or ny < 0 or (ny >= col) or (hospital[nx][ny] != 1):
						continue
					hospital[nx][ny] = 2
					q.append([nx, ny])
			if q:
				mins += 1
		if count == cnt:
			return mins
		return -1


class Solution:

	def helpaterp(self, hospital):
		r = len(hospital)
		c = len(hospital[0])
		result = 0
		que = []
		for i in range(r):
			for j in range(c):
				if hospital[i][j] == 2:
					que.append((i, j))
		que.append(-1)
		while que != []:
			flag = 0
			while que[0] != -1:
				pair = que.pop(0)
				i = pair[0]
				j = pair[1]
				if i > 0 and hospital[i - 1][j] == 1:
					hospital[i - 1][j] = 2
					que.append((i - 1, j))
					flag = 1
				if i + 1 < r and hospital[i + 1][j] == 1:
					hospital[i + 1][j] = 2
					que.append((i + 1, j))
					flag = 1
				if j > 0 and hospital[i][j - 1] == 1:
					hospital[i][j - 1] = 2
					que.append((i, j - 1))
					flag = 1
				if j + 1 < c and hospital[i][j + 1] == 1:
					hospital[i][j + 1] = 2
					que.append((i, j + 1))
					flag = 1
			if que[0] == -1:
				que.pop(0)
			if flag == 1:
				result += 1
			if que != []:
				que.append(-1)
		for i in range(r):
			for j in range(c):
				if hospital[i][j] == 1:
					return -1
		return result


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		m = len(hospital)
		n = len(hospital[0])
		visited = set()
		dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		q = deque()
		uninfected = 0
		for i in range(m):
			for j in range(n):
				if hospital[i][j] == 2:
					q.append((i, j))
				if hospital[i][j] == 1:
					uninfected += 1
		time = 0
		while q and uninfected > 0:
			for _ in range(len(q)):
				(i, j) = q.popleft()
				for (dr, dc) in dirs:
					(nr, nc) = (i + dr, j + dc)
					if nr >= 0 and nr < m and (nc >= 0) and (nc < n):
						if hospital[nr][nc] == 1:
							hospital[nr][nc] = 2
							q.append((nr, nc))
							uninfected -= 1
			time += 1
		return time if uninfected == 0 else -1
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		rc = input().split()
		r = int(rc[0])
		c = int(rc[1])
		hospital = []
		for i in range(r):
			hospital.append([int(j) for j in input().split()])
		ob = Solution()
		print(ob.helpaterp(hospital))


class Solution:

	def isvalid(self, i, j, m, n):
		if i >= 0 and j >= 0 and (j < m) and (i < n):
			return True
		return False

	def helpaterp(self, hospital):
		n = len(hospital)
		m = len(hospital[0])
		ans = 0
		q = []
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 2:
					q.append([i, j, 0])
		while q:
			x = q.pop(0)
			i = x[0]
			j = x[1]
			l = x[2]
			ni = i - 1
			nj = j
			if self.isvalid(ni, nj, m, n) and hospital[ni][nj] == 1:
				q.append([ni, nj, l + 1])
				hospital[ni][nj] = 2
			ni = i
			nj = j + 1
			if self.isvalid(ni, nj, m, n) and hospital[ni][nj] == 1:
				q.append([ni, nj, l + 1])
				hospital[ni][nj] = 2
			ni = i + 1
			nj = j
			if self.isvalid(ni, nj, m, n) and hospital[ni][nj] == 1:
				q.append([ni, nj, l + 1])
				hospital[ni][nj] = 2
			ni = i
			nj = j - 1
			if self.isvalid(ni, nj, m, n) and hospital[ni][nj] == 1:
				q.append([ni, nj, l + 1])
				hospital[ni][nj] = 2
			ans = max(ans, l)
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 1:
					return -1
		return ans
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		rc = input().split()
		r = int(rc[0])
		c = int(rc[1])
		hospital = []
		for i in range(r):
			hospital.append([int(j) for j in input().split()])
		ob = Solution()
		print(ob.helpaterp(hospital))


class Solution:

	def isValid(self, i, j, n, m, grid):
		return i >= 0 and i < n and (j >= 0) and (j < m) and (grid[i][j] == 1)

	def helpaterp(self, hospital):
		n = len(hospital)
		m = len(hospital[0])
		queue = []
		uninfected_pat = 0
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 2:
					queue.append((i, j))
				elif hospital[i][j] == 1:
					uninfected_pat += 1
		if uninfected_pat == 0:
			return 0
		time = 0
		while queue:
			size = len(queue)
			flag = 0
			while size > 0:
				(x1, y1) = queue.pop(0)
				ax = [1, -1, 0, 0]
				ay = [0, 0, 1, -1]
				for i in range(4):
					x = ax[i] + x1
					y = ay[i] + y1
					if self.isValid(x, y, n, m, hospital):
						flag = 1
						hospital[x][y] = 2
						queue.append((x, y))
				size -= 1
			if flag == 1:
				time += 1
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 1:
					return -1
		return time
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		rc = input().split()
		r = int(rc[0])
		c = int(rc[1])
		hospital = []
		for i in range(r):
			hospital.append([int(j) for j in input().split()])
		ob = Solution()
		print(ob.helpaterp(hospital))


class Solution:

	def helpaterp(self, hospital):
		(r, c) = (len(hospital), len(hospital[0]))
		que = []
		for i in range(r):
			for j in range(c):
				if hospital[i][j] == 2:
					que.append((i, j))
		matrix = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		(t, j) = (-1, len(que))
		while que:
			j -= 1
			q = que[0]
			que.remove(q)
			for m in matrix:
				x = q[0] + m[0]
				y = q[1] + m[1]
				if x < r and x >= 0 and (y < c) and (y >= 0):
					if hospital[x][y] == 1:
						que.append((x, y))
						hospital[x][y] = 2
			if j == 0:
				t += 1
				j = len(que)
		for i in range(r):
			for j in range(c):
				if hospital[i][j] == 1:
					return -1
		return t
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		rc = input().split()
		r = int(rc[0])
		c = int(rc[1])
		hospital = []
		for i in range(r):
			hospital.append([int(j) for j in input().split()])
		ob = Solution()
		print(ob.helpaterp(hospital))


class Solution:

	def helpaterp(self, grid):
		quew = []
		m = len(grid[0])
		n = len(grid)
		visited = [[False] * m for _ in range(n)]
		global ones
		ones = 0
		dx = [0, 0, 1, -1]
		dy = [1, -1, 0, 0]

		def add(p, quew):
			global ones
			for k in range(4):
				(i, j) = (p[0] + dx[k], p[1] + dy[k])
				if i >= 0 and j >= 0 and (i < n) and (j < m) and (grid[i][j] == 1) and (not visited[i][j]):
					visited[i][j] = True
					ones -= 1
					quew.append((i, j))
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					ones += 1
				elif grid[i][j] == 2:
					quew.append((i, j))
		time = 0
		if ones == 0:
			return 0
		while len(quew) != 0:
			for _ in range(len(quew)):
				cur = quew.pop(0)
				visited[cur[0]][cur[1]] = True
				add(cur, quew)
			time += 1
			if ones == 0:
				return time
		return -1
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		rc = input().split()
		r = int(rc[0])
		c = int(rc[1])
		hospital = []
		for i in range(r):
			hospital.append([int(j) for j in input().split()])
		ob = Solution()
		print(ob.helpaterp(hospital))


from collections import deque

class Solution:

	def helpaterp(self, h):
		(r, c) = (len(h), len(h[0]))
		q = deque()
		vis = set()
		cnt = 0
		for i in range(r):
			for j in range(c):
				if h[i][j] == 2:
					q.append([i, j])
					vis.add((i, j))
				elif h[i][j] == 0:
					cnt += 1
		ans = 0
		while q:
			f = 0
			for i in range(len(q)):
				(x, y) = q.popleft()
				for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
					(x1, y1) = (x + dx, y + dy)
					if 0 <= x1 < r and 0 <= y1 < c and ((x1, y1) not in vis) and (h[x1][y1] == 1):
						vis.add((x1, y1))
						q.append([x1, y1])
						f = 1
			if f:
				ans += 1
		if len(vis) != r * c - cnt:
			return -1
		return ans
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		rc = input().split()
		r = int(rc[0])
		c = int(rc[1])
		hospital = []
		for i in range(r):
			hospital.append([int(j) for j in input().split()])
		ob = Solution()
		print(ob.helpaterp(hospital))


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		grid = hospital
		m = len(grid)
		n = len(grid[0])
		a = deque()
		vis = [[False for i in range(n)] for i in range(m)]
		sum1 = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 2:
					a.append([i, j, 0])
					vis[i][j] = True
				if grid[i][j] == 1:
					sum1 = sum1 + 1
		time = 0
		drow = [-1, 0, 1, 0]
		dcol = [0, 1, 0, -1]
		while len(a) != 0:
			(r, c, t) = a.popleft()
			time = max(time, t)
			for i in range(4):
				nrow = r + drow[i]
				ncol = c + dcol[i]
				if nrow >= 0 and nrow < m and (ncol >= 0) and (ncol < n) and (grid[nrow][ncol] == 1) and (vis[nrow][ncol] == False):
					vis[nrow][ncol] = True
					a.append([nrow, ncol, t + 1])
		for i in range(m):
			for j in range(n):
				if vis[i][j] != True and grid[i][j] == 1:
					return -1
		return time
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		rc = input().split()
		r = int(rc[0])
		c = int(rc[1])
		hospital = []
		for i in range(r):
			hospital.append([int(j) for j in input().split()])
		ob = Solution()
		print(ob.helpaterp(hospital))


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		infected = 0
		uninfected = 0
		q = deque()
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] == 2:
					infected += 1
					q.append((i, j))
					hospital[i][j] = 0
				elif hospital[i][j] == 1:
					uninfected += 1
		if infected == 0:
			return -1
		if uninfected == 0:
			return 0
		time = 0
		while q:
			size = len(q)
			time += 1
			while size:
				(i, j) = q.popleft()
				for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
					r = i + dx
					c = j + dy
					if 0 <= r < len(hospital) and 0 <= c < len(hospital[0]) and (hospital[r][c] == 1):
						hospital[r][c] = 0
						q.append((r, c))
						uninfected -= 1
				size -= 1
			if uninfected == 0:
				break
		return time if uninfected == 0 else -1
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		rc = input().split()
		r = int(rc[0])
		c = int(rc[1])
		hospital = []
		for i in range(r):
			hospital.append([int(j) for j in input().split()])
		ob = Solution()
		print(ob.helpaterp(hospital))


from collections import deque

class Solution:

	def bfs(self, hosptial, visited, infectedPatients):
		count = 0
		stack = infectedPatients[:]
		while stack:
			for i in range(len(stack)):
				node = stack.pop(0)
				(row, col) = (node[0], node[1])
				if not visited[row][col]:
					visited[row][col] = True
					unvisitednodes = self.getUnvisitedNodes(row, col, visited, hospital)
					for unnode in unvisitednodes:
						stack.append(unnode)
			count += 1
		return count

	def getUnvisitedNodes(self, row, col, visited, A):
		unvisitednode = []
		directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		for direction in directions:
			rowVal = row + direction[0]
			colVal = col + direction[1]
			if rowVal >= 0 and rowVal < len(visited) and (colVal >= 0) and (colVal < len(visited[0])):
				if not visited[rowVal][colVal] and A[rowVal][colVal] != 0:
					unvisitednode.append([rowVal, colVal])
		return unvisitednode[:]

	def helpaterp(self, hospital):
		count = 0
		infectedPatients = []
		visited = [[False for j in range(len(hospital[0]))] for i in range(len(hospital))]
		totalCount = 0
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] == 2:
					infectedPatients.append([i, j])
		totalCount = self.bfs(hospital, visited, infectedPatients)
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] == 1 and (not visited[i][j]):
					return -1
		return totalCount - 1


from collections import deque

class Solution:

	def isAvailable(self, r, c, i, j):
		if i < 0 or i >= r or j < 0 or (j >= c):
			return False
		return True

	def helpaterp(self, hospi):
		r = len(hospi)
		c = len(hospi[0])
		moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
		q = deque([])
		visited = [[None for i in range(c)] for i in range(r)]
		for i in range(r):
			for j in range(c):
				if hospi[i][j] == 2:
					visited[i][j] = 0
					q.appendleft((i, j, 0))
				elif hospi[i][j] == 0:
					visited[i][j] = -1
		while len(q) > 0:
			(i, j, inf) = q.pop()
			for m in moves:
				(x, y) = (i + m[0], j + m[1])
				if self.isAvailable(r, c, x, y) and hospi[x][y] == 1 and (visited[x][y] == None or visited[x][y] > inf + 1):
					visited[x][y] = inf + 1
					q.appendleft((x, y, inf + 1))
		time = -float('inf')
		for i in range(r):
			for j in range(c):
				if visited[i][j] == None:
					return -1
				time = max(time, visited[i][j])
		return time


class Solution:

	def recur(self, i, j, visited, mat, dp):
		if i < 0 or j < 0 or i > len(mat) - 1 or (j > len(mat[0]) - 1) or (mat[i][j] == 0):
			return float('inf')
		if mat[i][j] == 2:
			return 0
		if visited[i][j]:
			if dp[i][j] != -1:
				return dp[i][j]
			return float('inf')
		visited[i][j] = True
		mn = float('inf')
		mn = min(mn, 1 + self.recur(i + 1, j, visited, mat, dp))
		mn = min(mn, 1 + self.recur(i - 1, j, visited, mat, dp))
		mn = min(mn, 1 + self.recur(i, j + 1, visited, mat, dp))
		mn = min(mn, 1 + self.recur(i, j - 1, visited, mat, dp))
		dp[i][j] = mn
		return mn

	def helpaterp(self, hospital):
		dp = [[-1 for i in range(len(hospital[0]))] for i in range(len(hospital))]
		visited = [[False for i in range(len(hospital[0]))] for i in range(len(hospital))]
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] == 1:
					visited[i][j] = False
					self.recur(i, j, visited, hospital, dp)
		mx = 0
		for i in dp:
			mx = max(mx, max(i))
		if mx == float('inf'):
			return -1
		return mx


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		dq = deque()
		(n, m) = (len(hospital), len(hospital[0]))
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 2:
					dq.append([i, j])
		count = 0
		while len(dq):
			loop = len(dq)
			flag = 0
			for _ in range(loop):
				(i, j) = dq.popleft()
				if i - 1 >= 0 and hospital[i - 1][j] == 1:
					hospital[i - 1][j] = 2
					dq.append([i - 1, j])
					flag = 1
				if i + 1 < n and hospital[i + 1][j] == 1:
					hospital[i + 1][j] = 2
					dq.append([i + 1, j])
					flag = 1
				if j - 1 >= 0 and hospital[i][j - 1] == 1:
					hospital[i][j - 1] = 2
					dq.append([i, j - 1])
					flag = 1
				if j + 1 < m and hospital[i][j + 1] == 1:
					hospital[i][j + 1] = 2
					dq.append([i, j + 1])
					flag = 1
			if flag:
				count += 1
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 1:
					return -1
		return count


class Solution:

	def helpaterp(self, hospital):
		row = len(hospital)
		col = len(hospital[0])
		q = []
		count = 0
		grid = hospital
		for i in range(row):
			for j in range(col):
				if hospital[i][j] == 2:
					q.append([i, j])
		while len(q) != 0:
			n = len(q)
			flag = False
			for k in range(n):
				i = q[0][0]
				j = q[0][1]
				q.pop(0)
				if self.valid(i + 1, j, row, col) and grid[i + 1][j] == 1:
					grid[i + 1][j] = 2
					q.append([i + 1, j])
					flag = True
				if self.valid(i - 1, j, row, col) and grid[i - 1][j] == 1:
					grid[i - 1][j] = 2
					q.append([i - 1, j])
					flag = True
				if self.valid(i, j + 1, row, col) and grid[i][j + 1] == 1:
					grid[i][j + 1] = 2
					q.append([i, j + 1])
					flag = True
				if self.valid(i, j - 1, row, col) and grid[i][j - 1] == 1:
					grid[i][j - 1] = 2
					q.append([i, j - 1])
					flag = True
			if flag == True:
				count += 1
		for i in range(row):
			for j in range(col):
				if grid[i][j] == 1:
					return -1
		return count

	def valid(self, i, j, row, col):
		if i < 0 or j < 0 or i >= row or (j >= col):
			return False
		return True


class Solution:

	def helpaterp(self, mat):
		from collections import deque
		q = deque()
		c = 0
		n = len(mat)
		m = len(mat[0])
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 1:
					c += 1
				if mat[i][j] == 2:
					q.append((i, j))
		ans = 0
		dx = [1, -1, 0, 0]
		dy = [0, 0, 1, -1]

		def isval(x, y):
			if x < 0 or y < 0 or x >= n or (y >= m):
				return False
			return mat[x][y] == 1
		while q:
			ans += 1
			for _ in range(len(q)):
				t = q.popleft()
				for i in range(4):
					if isval(t[0] + dx[i], t[1] + dy[i]):
						mat[t[0] + dx[i]][t[1] + dy[i]] = 2
						q.append((t[0] + dx[i], t[1] + dy[i]))
						c -= 1
		if c == 0:
			return ans - 1
		return -1


class Solution:

	def helpaterp(self, hospital):

		def is_valid(mat, i, j):
			nrows = len(mat)
			ncols = len(mat[0])
			if not (i >= 0 and i < nrows):
				return False
			if not (j >= 0 and j < ncols):
				return False
			return True

		def get_neighbours(mat, p, q):
			res = []
			for (r, s) in [(p - 1, q), (p + 1, q), (p, q - 1), (p, q + 1)]:
				if is_valid(mat, r, s):
					if mat[r][s] == 1:
						res.append((r, s))
			return res

		def bfs_one_iteration(possible_sources, d1, visited, uninfected_people, mat):
			done_once = False
			for src in possible_sources:
				if len(d1[src]['q']) == 0:
					continue
				done_once = True
				curr = d1[src]['q'].popleft()
				visited[curr] = True
				if curr in uninfected_people:
					uninfected_people.remove(curr)
				(x, y) = curr
				neighbours = get_neighbours(mat, x, y)
				for e in neighbours:
					if e not in visited:
						d1[src]['q'].append(e)
						d1[src]['level'][e] = d1[src]['level'][curr] + 1
			return done_once

		def bfs_all_src(possible_sources, uninfected_people, mat):
			from collections import deque
			d1 = {src: {'q': deque(), 'level': {src: 0}} for src in possible_sources}
			visited = {}
			for src in possible_sources:
				d1[src]['q'].append(src)
			done_alteast_once = True
			while done_alteast_once and len(uninfected_people) > 0:
				done_alteast_once = bfs_one_iteration(possible_sources, d1, visited, uninfected_people, mat)
			max_time = -1
			if len(uninfected_people) == 0:
				max_time = max([max(d1[k]['level'].values()) for k in d1])
			return max_time

		def func(mat):
			nrows = len(mat)
			ncols = len(mat[0])
			possible_sources = [(i, j) for i in range(nrows) for j in range(ncols) if mat[i][j] == 2]
			uninfected_people = set([(i, j) for i in range(nrows) for j in range(ncols) if mat[i][j] == 1])
			res = bfs_all_src(possible_sources, uninfected_people, mat)
			return res
		res1 = func(hospital)
		return res1


class Solution:

	def spread(self, hospital, i, j, q):
		if j + 1 < len(hospital[0]) and hospital[i][j + 1] == 1:
			hospital[i][j + 1] = 2
			q.append((i, j + 1))
		if j - 1 >= 0 and hospital[i][j - 1] == 1:
			hospital[i][j - 1] = 2
			q.append((i, j - 1))
		if i + 1 < len(hospital) and hospital[i + 1][j] == 1:
			hospital[i + 1][j] = 2
			q.append((i + 1, j))
		if i - 1 >= 0 and hospital[i - 1][j] == 1:
			hospital[i - 1][j] = 2
			q.append((i - 1, j))

	def helpaterp(self, hospital):
		count = 0
		q = []
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] == 2:
					q.append((i, j))
		while q:
			size = len(q)
			count += 1
			for i in range(size):
				patient = q.pop(0)
				self.spread(hospital, patient[0], patient[1], q)
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] == 1:
					return -1
		return count - 1


class Queue(object):

	def __init__(self, *args):
		self.list = []
		self.list += args

	def isEmpty(self):
		return len(self.list) == 0

	def push(self, obj):
		self.list.append(obj)

	def pop(self, x=-1):
		return self.list.pop(x)

class Solution:

	def helpaterp(self, grid):
		(m, n) = (len(grid), len(grid[0]))
		dir = ((0, 1), (1, 0), (-1, 0), (0, -1))
		freshleft = 0
		queue = Queue()

		def isValid(i, j):
			return i >= 0 and i < m and (j >= 0) and (j < n)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					freshleft += 1
				elif grid[i][j] == 2:
					queue.push([i, j, 0])
		minn = 0
		while not queue.isEmpty() and freshleft > 0:
			cur = queue.pop(0)
			for k in range(4):
				(nx, ny, nt) = (cur[0] + dir[k][0], cur[1] + dir[k][1], cur[2] + 1)
				if not isValid(nx, ny) or grid[nx][ny] == 0 or grid[nx][ny] == 2:
					continue
				grid[nx][ny] = 2
				freshleft -= 1
				queue.push([nx, ny, nt])
				minn = nt
		return minn if freshleft == 0 else -1


class Solution:

	def helpaterp(self, hospital):
		r = len(hospital)
		c = len(hospital[0])
		vis = [[False for i in range(c)] for j in range(r)]
		q1 = []
		q2 = []
		for i in range(r):
			for j in range(c):
				if hospital[i][j] == 2:
					q1.append((i, j))
					vis[i][j] = True
		timer = 0
		while len(q1) != 0:
			temp = q1.pop()
			i = temp[0]
			j = temp[1]
			if i - 1 != -1 and vis[i - 1][j] == False:
				if hospital[i - 1][j] == 1:
					vis[i - 1][j] = True
					q2.append((i - 1, j))
			if i + 1 != r and vis[i + 1][j] == False:
				if hospital[i + 1][j] == 1:
					vis[i + 1][j] = True
					q2.append((i + 1, j))
			if j - 1 != -1 and vis[i][j - 1] == False:
				if hospital[i][j - 1] == 1:
					vis[i][j - 1] = True
					q2.append((i, j - 1))
			if j + 1 != c and vis[i][j + 1] == False:
				if hospital[i][j + 1] == 1:
					vis[i][j + 1] = True
					q2.append((i, j + 1))
			if len(q1) == 0:
				if len(q2) == 0:
					break
				timer += 1
				q1 = q2[:]
				q2 = []
		for i in range(r):
			for j in range(c):
				if hospital[i][j] == 1 and vis[i][j] == False:
					return -1
		return timer


class Solution:

	def helpaterp(self, hospital):
		normal = 0
		infected = []
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] == 1:
					normal += 1
				if hospital[i][j] == 2:
					infected.append((i, j))
		time = 0
		dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		while infected:
			time += 1
			infected_next = []
			for (i, j) in infected:
				for (x, y) in dirs:
					(a, b) = (i + x, j + y)
					if 0 <= a < len(hospital) and 0 <= b < len(hospital[0]):
						if hospital[a][b] == 0 or hospital[a][b] == 2:
							continue
						infected_next.append((a, b))
						hospital[a][b] = 2
						normal -= 1
						if normal == 0:
							return time
			infected = infected_next[:]
		return -1


class cell:

	def __init__(self, x, y):
		self.x = x
		self.y = y

class Solution:

	def helpaterp(self, h):
		q = []
		visit = [[False for i in range(c)] for i in range(r)]
		for i in range(r):
			for j in range(c):
				if h[i][j] == 2:
					q.append(cell(i, j))
					visit[i][j] = True
		ans = 0
		while len(q):
			s = len(q)
			while s > 0:
				t = q[0]
				if t.x - 1 >= 0 and h[t.x - 1][t.y] == 1 and (visit[t.x - 1][t.y] == False):
					h[t.x - 1][t.y] = 2
					q.append(cell(t.x - 1, t.y))
					visit[t.x - 1][t.y] = True
				if t.x + 1 < r and h[t.x + 1][t.y] == 1 and (visit[t.x + 1][t.y] == False):
					h[t.x + 1][t.y] = 2
					q.append(cell(t.x + 1, t.y))
					visit[t.x + 1][t.y] = True
				if t.y - 1 >= 0 and h[t.x][t.y - 1] == 1 and (visit[t.x][t.y - 1] == False):
					h[t.x][t.y - 1] = 2
					q.append(cell(t.x, t.y - 1))
					visit[t.x][t.y - 1] = True
				if t.y + 1 < c and h[t.x][t.y + 1] == 1 and (visit[t.x][t.y + 1] == False):
					h[t.x][t.y + 1] = 2
					q.append(cell(t.x, t.y + 1))
					visit[t.x][t.y + 1] = True
				q.pop(0)
				s -= 1
			ans += 1
		for i in range(r):
			for j in range(c):
				if h[i][j] == 1:
					return -1
		return ans - 1


from collections import deque

class Solution:
	ar = [0, 0, 1, -1]
	ac = [1, -1, 0, 0]

	def helpaterp(self, hospital):
		nr = len(hospital)
		nc = len(hospital[0])
		visited = [[False for _ in range(nc)] for _ in range(nr)]
		q = deque()
		patients = 0
		for r in range(nr):
			for c in range(nc):
				if hospital[r][c] == 2:
					q.append((r, c))
				if hospital[r][c] != 0:
					patients += 1
		count = 0
		timer = 0
		while q:
			infected = len(q)
			count += infected
			while infected != 0:
				(x, y) = q.popleft()
				infected -= 1
				for i in range(len(self.ar)):
					xx = x + self.ar[i]
					yy = y + self.ac[i]
					if xx >= 0 and xx < nr and (yy >= 0) and (yy < nc) and (hospital[xx][yy] == 1):
						hospital[xx][yy] = 2
						q.append((xx, yy))
			if len(q) > 0:
				timer += 1
		if patients == count:
			return timer
		return -1


class Solution:

	def helpaterp(self, hospital):
		row = len(hospital)
		col = len(hospital[0])
		visited = [[False for _ in range(col)] for _ in range(row)]

		def find(i, j):
			if hospital[i][j] == 2:
				return 0
			visited[i][j] = True
			tp = []
			if i > 0 and (not visited[i - 1][j]) and (hospital[i - 1][j] != 0):
				c = find(i - 1, j)
				if c != -1:
					tp.append(c)
			if j > 0 and (not visited[i][j - 1]) and (hospital[i][j - 1] != 0):
				c = find(i, j - 1)
				if c != -1:
					tp.append(c)
			if i < row - 1 and (not visited[i + 1][j]) and (hospital[i + 1][j] != 0):
				c = find(i + 1, j)
				if c != -1:
					tp.append(c)
			if j < col - 1 and (not visited[i][j + 1]) and (hospital[i][j + 1] != 0):
				c = find(i, j + 1)
				if c != -1:
					tp.append(c)
			visited[i][j] = False
			if len(tp) == 0:
				return -1
			return 1 + min(tp)
		ans = 0
		for i in range(row):
			for j in range(col):
				if hospital[i][j] == 1:
					tp = find(i, j)
					if tp == -1:
						return -1
					ans = max(tp, ans)
		return ans


class Solution:

	def helpaterp(self, hospital):
		(m, n) = (len(hospital), len(hospital[0]))
		minimum = [[0 for i in range(n)] for j in range(m)]
		visited = [[False for i in range(n)] for j in range(m)]
		for i in range(m):
			for j in range(n):
				if hospital[i][j] == 1:
					minimum[i][j] = 99999

		def possible(i, j, m, n):
			return i >= 0 and j >= 0 and (i < m) and (j < n)

		def bfs(i, j, grid, m, n):
			q = []
			q.append([i, j, 0])
			while q:
				curr = q.pop(0)
				(i, j, t) = (curr[0], curr[1], curr[2])
				a = [-1, 0, 1, 0]
				b = [0, 1, 0, -1]
				for k in range(4):
					(r, c) = (i + a[k], j + b[k])
					if possible(r, c, m, n):
						if visited[r][c] == False:
							if grid[r][c] == 1:
								q.append([r, c, t + 1])
								minimum[r][c] = min(minimum[r][c], t + 1)
								visited[r][c] = True
							elif grid[r][c] == 2:
								q.append([r, c, 0])
								visited[r][c] = True
							else:
								continue
						elif grid[r][c] == 1:
							if minimum[r][c] > t + 1:
								q.append([r, c, t + 1])
								minimum[r][c] = min(minimum[r][c], t + 1)
		output = -99
		for i in range(m):
			for j in range(n):
				if hospital[i][j] == 2 and visited[i][j] == False:
					visited[i][j] = True
					bfs(i, j, hospital, m, n)
		mx = -999
		for i in range(m):
			for j in range(n):
				mx = max(mx, minimum[i][j])
		if mx == 99999:
			return -1
		return mx


class Solution:

	def helpaterp(self, hospital):
		grid = hospital
		queue = []
		time = 0
		fresh = 0
		(rows, cols) = (len(grid), len(grid[0]))
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] == 1:
					fresh += 1
				if grid[i][j] == 2:
					queue.append([i, j])
		while len(queue) > 0 and fresh > 0:
			for i in range(len(queue)):
				(r, c) = queue.pop(0)
				directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
				for (dr, dc) in directions:
					(row, col) = (r + dr, c + dc)
					if row >= 0 and col >= 0 and (row < rows) and (col < cols) and (grid[row][col] == 1):
						grid[row][col] = 2
						queue.append([row, col])
						fresh -= 1
			time += 1
		if fresh > 0:
			return -1
		return time


def dfs(grid, i, j, time, prev_time):
	m = len(grid)
	n = len(grid[0])
	if i < 0 or j < 0 or i >= m or (j >= n) or (grid[i][j] != 1):
		return
	if time[i][j] == -1:
		time[i][j] = prev_time + 1
	else:
		time[i][j] = min(time[i][j], prev_time + 1)
	grid[i][j] = -1
	dfs(grid, i + 1, j, time, time[i][j])
	dfs(grid, i - 1, j, time, time[i][j])
	dfs(grid, i, j + 1, time, time[i][j])
	dfs(grid, i, j - 1, time, time[i][j])
	grid[i][j] = 1

class Solution:

	def helpaterp(self, grid):
		m = len(grid)
		n = len(grid[0])
		count = 0
		time = [[-1 for i in range(n)] for j in range(m)]
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 2:
					time[i][j] = 0
					dfs(grid, i + 1, j, time, 0)
					dfs(grid, i - 1, j, time, 0)
					dfs(grid, i, j + 1, time, 0)
					dfs(grid, i, j - 1, time, 0)
		ans = -1
		for i in range(m):
			for j in range(n):
				ans = max(ans, time[i][j])
				if grid[i][j] == 1 and time[i][j] == -1:
					return -1
		return ans


import collections

class Solution:

	def helpaterp(self, hospital):
		ROWS = len(hospital)
		COLS = len(hospital[0])
		q = collections.deque()
		uninfected = 0
		for r in range(ROWS):
			for c in range(COLS):
				if hospital[r][c] == 2:
					q.append((r, c))
				if hospital[r][c] == 1:
					uninfected += 1

		def infectAll(r, c):
			nonlocal uninfected
			if r not in range(ROWS) or c not in range(COLS):
				return
			if hospital[r][c] == 0 or hospital[r][c] == 2:
				return
			hospital[r][c] = 2
			uninfected -= 1
			q.append((r, c))
			return
		time = 0
		while q and uninfected:
			time += 1
			size = len(q)
			for i in range(size):
				(r, c) = q.popleft()
				infectAll(r - 1, c)
				infectAll(r, c + 1)
				infectAll(r + 1, c)
				infectAll(r, c - 1)
		if uninfected == 0:
			return time
		return -1


import collections

class Solution:

	def helpaterp(self, hospital):
		ROWS = len(hospital)
		COLS = len(hospital[0])
		q = collections.deque()
		visited = set()
		time = -1
		for r in range(ROWS):
			for c in range(COLS):
				if hospital[r][c] == 2:
					q.append((r, c))
					visited.add((r, c))

		def infectAll(r, c):
			if r not in range(ROWS) or c not in range(COLS):
				return
			if (r, c) in visited:
				return
			if hospital[r][c] == 0 or hospital[r][c] == 2:
				return
			if hospital[r][c] == 1:
				hospital[r][c] = 2
			q.append((r, c))
			visited.add((r, c))
			return
		while q:
			size = len(q)
			for i in range(size):
				(r, c) = q.popleft()
				infectAll(r - 1, c)
				infectAll(r, c + 1)
				infectAll(r + 1, c)
				infectAll(r, c - 1)
			time += 1
		for r in range(ROWS):
			for c in range(COLS):
				if hospital[r][c] == 1:
					return -1
		return time


class Solution:

	def helpaterp(self, hospital):
		numberOfOnes = 0
		queue = []
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] == 1:
					numberOfOnes += 1
				elif hospital[i][j] == 2:
					queue.append([i, j])
		ans = 0
		while len(queue) and numberOfOnes > 0:
			length = len(queue)
			while length > 0:
				(x, y) = queue.pop(0)
				for (dx, dy) in [[-1, 0], [0, 1], [1, 0], [0, -1]]:
					xx = x + dx
					yy = y + dy
					if self.isValid(xx, yy, hospital) and hospital[xx][yy] == 1:
						numberOfOnes -= 1
						hospital[xx][yy] = 2
						queue.append([xx, yy])
				length -= 1
			ans += 1
		if numberOfOnes == 0:
			return ans
		else:
			return -1

	def isValid(self, x, y, hospital):
		if x >= 0 and y >= 0 and (x < len(hospital)) and (y < len(hospital[0])) and (hospital[x][y] != 0):
			return True
		else:
			return False


def safe(M, i, j, R, C):
	for (u, v) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
		if 0 <= u < R and 0 <= v < C and (M[u][v] == 2):
			return False
	return True

class Solution:

	def helpaterp(self, M):
		(R, C) = (len(M), len(M[0]))
		healthy = []
		for i in range(R):
			for j in range(C):
				if M[i][j] == 1:
					healthy.append((i, j))
		ans = 0
		prevcnt = R * C + 1
		tmp = []
		infected = []
		while healthy and prevcnt != len(healthy):
			prevcnt = len(healthy)
			for (i, j) in healthy:
				if safe(M, i, j, R, C):
					tmp.append((i, j))
				else:
					infected.append((i, j))
			for (i, j) in infected:
				M[i][j] = 2
			(healthy, tmp) = (tmp, healthy)
			tmp.clear()
			infected.clear()
			ans += 1
		return -1 if healthy else ans


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		rows = len(hospital)
		cols = len(hospital[0])
		queue = deque()
		uninfected_count = 0
		time = 0
		for i in range(rows):
			for j in range(cols):
				if hospital[i][j] == 1:
					uninfected_count += 1
				if hospital[i][j] == 2:
					queue.append((i, j))
		while len(queue) > 0 and uninfected_count > 0:
			time += 1
			for _ in range(len(queue)):
				(i, j) = queue.popleft()
				for (x, y) in [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]:
					if x >= 0 and y >= 0 and (x < rows) and (y < cols) and (hospital[x][y] == 1):
						uninfected_count -= 1
						queue.append((x, y))
						hospital[x][y] = 2
		if uninfected_count > 0:
			return -1
		else:
			return time


class Solution:

	def helpaterp(self, hospital):
		r = len(hospital)
		c = len(hospital[0])
		time = 0
		q = []
		for i in range(r):
			for j in range(c):
				if hospital[i][j] == 2:
					q.append((i, j))
		count = len(q)
		while count > 0:
			for i in range(count):
				(i, j) = q.pop(0)
				self.push_neighbours(i, j, q, r, c, hospital)
			count = len(q)
			if count > 0:
				time += 1
		for i in range(r):
			for j in range(c):
				if hospital[i][j] == 1:
					return -1
		return time

	def push_neighbours(self, i, j, q, r, c, grid):
		x = [-1, 1, 0, 0]
		y = [0, 0, -1, 1]
		for l in range(len(x)):
			if i + x[l] < 0 or i + x[l] >= r or j + y[l] < 0 or (j + y[l] >= c) or (grid[i + x[l]][j + y[l]] != 1):
				continue
			q.append((i + x[l], j + y[l]))
			grid[i + x[l]][j + y[l]] = 2


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		q = deque()
		rows = len(hospital)
		cols = len(hospital[0])
		for row in range(rows):
			for col in range(cols):
				if hospital[row][col] == 2:
					q.append((row, col, 0))
		while q:
			(row, col, level) = q.popleft()
			for (x, y) in [(row, col - 1), (row, col + 1), (row - 1, col), (row + 1, col)]:
				if 0 <= x < rows and 0 <= y < cols and (hospital[x][y] == 1):
					hospital[x][y] = 2
					q.append((x, y, level + 1))
		for i in range(rows):
			for j in range(cols):
				if hospital[i][j] == 1:
					return -1
		return level


class Solution:

	def helpaterp(self, mat):
		n = len(mat)
		m = len(mat[0])
		cnt = 0
		inf = 0
		ans = 0
		q = []
		dx = [-1, 1, 0, 0]
		dy = [0, 0, -1, 1]
		for i in range(n):
			for j in range(m):
				if mat[i][j] != 0:
					cnt += 1
				if mat[i][j] == 2:
					q.append((i, j))
		while q:
			k = len(q)
			inf += k
			while k:
				rem = q.pop(0)
				x = rem[0]
				y = rem[1]
				for i in range(4):
					nx = x + dx[i]
					ny = y + dy[i]
					if nx >= 0 and ny >= 0 and (nx < n) and (ny < m) and (mat[nx][ny] == 1):
						q.append((nx, ny))
						mat[nx][ny] = 2
				k -= 1
			if q:
				ans += 1
		if inf == cnt:
			return ans
		return -1


from collections import deque

class Solution:
	DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))

	def inHospital(self, i, j, n, m):
		return 0 <= i < n and 0 <= j < m

	def helpaterp(self, hospital):
		n = len(hospital)
		m = len(hospital[0])
		q = deque()
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 2:
					q.append((i, j))
		time = 0
		while q:
			for _ in range(len(q)):
				(i, j) = q.popleft()
				for dir in self.DIRS:
					ii = i + dir[0]
					jj = j + dir[1]
					if self.inHospital(ii, jj, n, m) and hospital[ii][jj] == 1:
						hospital[ii][jj] = 2
						q.append((ii, jj))
			if q:
				time += 1
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 1:
					return -1
		return time


class Solution:

	def __init__(self):
		self.curr_nodes = []
		self.time_steps = 0
		self.elements_visited = 0
		self.total_patients = 0

	def helpaterp(self, hospital):
		self.m = len(hospital)
		self.n = len(hospital[0])
		self.hospital = hospital
		for i in range(self.m):
			for j in range(self.n):
				if self.hospital[i][j] == 2:
					self.curr_nodes.append([i, j])
					self.elements_visited += 1
					self.total_patients += 1
				if self.hospital[i][j] == 1:
					self.total_patients += 1
		self.perform_bfs()
		if self.elements_visited < self.total_patients:
			return -1
		return self.time_steps - 1

	def perform_bfs(self):
		while len(self.curr_nodes) != 0:
			new_curr_nodes = []
			for node_ele in self.curr_nodes:
				all_poss_neigh = [[0, -1], [0, 1], [1, 0], [-1, 0]]
				for neigh_ele in all_poss_neigh:
					if self.check_neigh(node_ele[0] + neigh_ele[0], node_ele[1] + neigh_ele[1]):
						new_curr_nodes.append([node_ele[0] + neigh_ele[0], node_ele[1] + neigh_ele[1]])
						self.hospital[node_ele[0] + neigh_ele[0]][node_ele[1] + neigh_ele[1]] = 2
						self.elements_visited += 1
			self.time_steps += 1
			self.curr_nodes = list(new_curr_nodes)

	def check_neigh(self, i, j):
		if i >= 0 and i < self.m and (j >= 0) and (j < self.n) and (self.hospital[i][j] == 1):
			return True
		return False


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		q = deque()
		res = 0
		(rows, cols) = (len(hospital), len(hospital[0]))
		for i in range(rows):
			for j in range(cols):
				if hospital[i][j] == 2:
					q.append([i, j])
		while q:
			n = len(q)
			count = 0
			for i in range(n):
				(i, j) = q.popleft()
				if i + 1 < rows and hospital[i + 1][j] == 1:
					hospital[i + 1][j] = 2
					q.append([i + 1, j])
				if i - 1 >= 0 and hospital[i - 1][j] == 1:
					hospital[i - 1][j] = 2
					q.append([i - 1, j])
				if j + 1 < cols and hospital[i][j + 1] == 1:
					hospital[i][j + 1] = 2
					q.append([i, j + 1])
				if j - 1 >= 0 and hospital[i][j - 1] == 1:
					hospital[i][j - 1] = 2
					q.append([i, j - 1])
			if len(q) > 0:
				res += 1
		for i in range(rows):
			for j in range(cols):
				if hospital[i][j] == 1:
					return -1
		return res


class Solution:

	def helpaterp(self, hospital):
		n = len(hospital)
		m = len(hospital[0])
		visited = [[0 for _ in range(m)] for _ in range(n)]
		row = [-1, 1, 0, 0]
		col = [0, 0, -1, 1]

		def isvalid(i, j):
			if (i >= 0 and i < n) and (j >= 0 and j < m):
				return 1
			return 0
		time = 0
		q = []
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 2:
					q.append([[i, j], 0])
		i = 0
		while i != len(q):
			k = q[i][0]
			t = q[i][1]
			visited[k[0]][k[1]] = 1
			for j in range(4):
				x = k[0] + row[j]
				y = k[1] + col[j]
				if isvalid(x, y) and visited[x][y] == 0 and (hospital[x][y] == 1):
					hospital[x][y] = 2
					q.append([[x, y], t + 1])
					time = max(time, q[-1][1])
			i += 1
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 1:
					time = -1
					break
		return time


class Solution:

	def helpaterp(self, hospital):
		(m, n) = (len(hospital), len(hospital[0]))

		def isValid(x, y):
			if x < 0 or x >= m or y < 0 or (y >= n):
				return False
			if hospital[x][y] != 1:
				return False
			if (x, y) in vis:
				return False
			return True
		vis = set()
		q = []
		time = [[0 for i in range(n)] for j in range(m)]
		for i in range(m):
			for j in range(n):
				if hospital[i][j] == 2:
					q.append((i, j))
		dx = [0, 0, 1, -1]
		dy = [1, -1, 0, 0]
		while q:
			cur = q.pop(0)
			X = cur[0]
			Y = cur[1]
			for i in range(4):
				if isValid(X + dx[i], Y + dy[i]):
					time[X + dx[i]][Y + dy[i]] = time[X][Y] + 1
					q.append((X + dx[i], Y + dy[i]))
					vis.add((X + dx[i], Y + dy[i]))
					hospital[X + dx[i]][Y + dy[i]] = 2
		res = 0
		for i in range(m):
			for j in range(n):
				if hospital[i][j] == 1:
					return -1
				res = max(res, time[i][j])
		return res


class Solution:

	def helpaterp(self, hos):
		q = []
		(n, m) = (len(hos), len(hos[0]))
		for i in range(n):
			for j in range(m):
				if hos[i][j] == 2:
					q.append([i, j])
		c = 0
		while q:
			loop = len(q)
			flag = 0
			for _ in range(loop):
				(i, j) = q.pop(0)
				if i - 1 >= 0 and hos[i - 1][j] == 1:
					hos[i - 1][j] = 2
					q.append([i - 1, j])
					flag = 1
				if i + 1 < n and hos[i + 1][j] == 1:
					hos[i + 1][j] = 2
					q.append([i + 1, j])
					flag = 1
				if j - 1 >= 0 and hos[i][j - 1] == 1:
					hos[i][j - 1] = 2
					q.append([i, j - 1])
					flag = 1
				if j + 1 < m and hos[i][j + 1] == 1:
					hos[i][j + 1] = 2
					q.append([i, j + 1])
					flag = 1
			if flag:
				c += 1
		for i in range(n):
			for j in range(m):
				if hos[i][j] == 1:
					return -1
		return c


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		dq = deque()
		(row, col) = (len(hospital), len(hospital[0]))
		for i in range(row):
			for j in range(col):
				if hospital[i][j] == 2:
					dq.append([i, j])
		global time
		time = 0

		def maxtime():
			global time
			check = 0
			for k in range(len(dq)):
				rowad = [-1, 1, 0, 0]
				colad = [0, 0, -1, 1]
				(i, j) = dq.popleft()
				for l in range(4):
					i1 = i + rowad[l]
					j1 = j + colad[l]
					if i1 >= 0 and j1 >= 0 and (i1 < row) and (j1 < col) and (hospital[i1][j1] == 1):
						dq.append([i1, j1])
						hospital[i1][j1] = 2
						check = 1
			if check == 1:
				time += 1
				maxtime()
		maxtime()
		for i in range(row):
			for j in range(col):
				if hospital[i][j] == 1:
					return -1
		return time


class Solution:

	def helpaterp(self, hospital):
		q = []
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] == 2:
					q.append([i, j, 0])
		dx = [1, -1, 0, 0]
		dy = [0, 0, 1, -1]
		while q:
			x = q.pop(0)
			i = x[0]
			j = x[1]
			for k in range(4):
				ik = i + dx[k]
				jk = j + dy[k]
				if ik >= 0 and ik < len(hospital) and (jk >= 0) and (jk < len(hospital[0])) and (hospital[ik][jk] == 1):
					hospital[ik][jk] = 2
					q.append([ik, jk, x[2] + 1])
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] == 1:
					return -1
		return x[2]


class Solution:

	def helpaterp(self, hospital):
		queue = []
		for y in range(0, len(hospital)):
			for x in range(0, len(hospital[y])):
				if hospital[y][x] == 2:
					queue.append([y, x, 0])
		res = 0
		while queue:
			curr = queue.pop(0)
			X = curr[1]
			Y = curr[0]
			res = max(res, curr[2])
			hospital[Y][X] = 2
			dx = [1, -1, 0, 0]
			dy = [0, 0, 1, -1]
			for i in range(4):
				newX = X + dx[i]
				newY = Y + dy[i]
				if newX >= 0 and newX < len(hospital[0]) and (newY >= 0) and (newY < len(hospital)) and (hospital[newY][newX] == 1):
					queue.append([newY, newX, curr[2] + 1])
		for y in range(0, len(hospital)):
			for x in range(0, len(hospital[y])):
				if hospital[y][x] == 1:
					return -1
		return res


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		h = deque()
		n = len(hospital)
		m = len(hospital[0])
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 2:
					h.append((i, j, 0))
		sol = 0
		while h:
			(i, j, t) = h.popleft()
			sol = max(sol, t)
			if i > 0 and hospital[i - 1][j] == 1:
				hospital[i - 1][j] = 2
				h.append((i - 1, j, t + 1))
			if i < n - 1 and hospital[i + 1][j] == 1:
				hospital[i + 1][j] = 2
				h.append((i + 1, j, t + 1))
			if j > 0 and hospital[i][j - 1] == 1:
				hospital[i][j - 1] = 2
				h.append((i, j - 1, t + 1))
			if j < m - 1 and hospital[i][j + 1] == 1:
				hospital[i][j + 1] = 2
				h.append((i, j + 1, t + 1))
		for i in range(n):
			for j in range(m):
				if hospital[i][j] == 1:
					return -1
		return sol


class Solution:

	def helpaterp(self, grid):
		level = -1
		q = []
		(rows, cols) = (len(grid), len(grid[0]))
		for row in range(rows):
			for col in range(cols):
				if grid[row][col] == 2:
					q.append((row, col))
		while q:
			temp = []
			while q:
				(row, col) = q.pop(0)
				neis = [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]
				for (row, col) in neis:
					if 0 <= row < rows and 0 <= col < cols:
						if grid[row][col] in [0, 2]:
							continue
						grid[row][col] = 2
						temp.append((row, col))
			q = temp
			level += 1
		for row in range(rows):
			for col in range(cols):
				if grid[row][col] == 1:
					return -1
		return level


from collections import deque

class Solution:

	def isavailable(self, x, y, hospital):
		R = len(hospital)
		C = len(hospital[0])
		if x < 0 or x >= R or y < 0 or (y >= C) or (hospital[x][y] != 1):
			return False
		return True

	def traverseInfect(self, i, j, hospital, visible):
		rows = [-1, +1, 0, 0]
		cols = [0, 0, -1, +1]
		queue = deque([])
		infLevel = 0
		visible[i][j] = 0
		queue.appendleft((i, j, infLevel))
		while len(queue) > 0:
			(x1, y1, il) = queue.pop()
			for ind in range(len(rows)):
				(dx, dy) = (rows[ind], cols[ind])
				(x2, y2) = (x1 + dx, y1 + dy)
				if self.isavailable(x2, y2, hospital) and (visible[x2][y2] is None or visible[x2][y2] > il + 1):
					visible[x2][y2] = il + 1
					queue.appendleft((x2, y2, il + 1))

	def helpaterp(self, hospital):
		R = len(hospital)
		C = len(hospital[0])
		visible = [[None for i in range(C)] for i in range(R)]
		for i in range(R):
			for j in range(C):
				if hospital[i][j] == 2:
					self.traverseInfect(i, j, hospital, visible)
		maxtime = -float('inf')
		for i in range(R):
			for j in range(C):
				if hospital[i][j] == 1 and visible[i][j] is None:
					return -1
				elif hospital[i][j] == 1:
					maxtime = max(maxtime, visible[i][j])
		return maxtime


class Solution:

	def helpaterp(self, hospital):
		q = []
		uninfected = 0
		for i in range(len(hospital)):
			for j in range(len(hospital[0])):
				if hospital[i][j] == 2:
					q.append([i, j, 0])
				elif hospital[i][j] == 1:
					uninfected += 1
		dirt = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		while len(q):
			(i, j, level) = q.pop(0)
			for (x, y) in dirt:
				if 0 <= i + x < len(hospital) and 0 <= y + j < len(hospital[0]) and (hospital[i + x][y + j] == 1):
					q.append([i + x, y + j, level + 1])
					hospital[i + x][y + j] = 2
					uninfected -= 1
		if uninfected != 0:
			return -1
		return level


class Solution:

	def helpaterp(self, mat):
		rotten = []
		(r, c, fresh, t) = (len(mat), len(mat[0]), 0, 0)
		for i in range(r):
			for j in range(c):
				if mat[i][j] == 2:
					rotten.append([i, j])
				elif mat[i][j] == 1:
					fresh += 1
		while len(rotten) > 0:
			num = len(rotten)
			for i in range(num):
				(x, y) = rotten[0]
				rotten.pop(0)
				if x > 0 and mat[x - 1][y] == 1:
					mat[x - 1][y] = 2
					fresh -= 1
					rotten.append([x - 1, y])
				if y > 0 and mat[x][y - 1] == 1:
					mat[x][y - 1] = 2
					fresh -= 1
					rotten.append([x, y - 1])
				if x < r - 1 and mat[x + 1][y] == 1:
					mat[x + 1][y] = 2
					fresh -= 1
					rotten.append([x + 1, y])
				if y < c - 1 and mat[x][y + 1] == 1:
					mat[x][y + 1] = 2
					fresh -= 1
					rotten.append([x, y + 1])
			if len(rotten) > 0:
				t += 1
		if fresh == 0:
			return t
		else:
			return -1


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		queue = deque()
		(r, c) = (len(hospital), len(hospital[0]))
		for i in range(r):
			for j in range(c):
				if hospital[i][j] == 2:
					queue.append([i, j])
		cnt = 0
		while len(queue):
			loop = len(queue)
			flag = 0
			for i in range(loop):
				(a, b) = queue.popleft()
				if a - 1 >= 0 and hospital[a - 1][b] == 1:
					hospital[a - 1][b] = 2
					queue.append([a - 1, b])
					flag = 1
				if a + 1 < r and hospital[a + 1][b] == 1:
					hospital[a + 1][b] = 2
					queue.append([a + 1, b])
					flag = 1
				if b - 1 >= 0 and hospital[a][b - 1] == 1:
					hospital[a][b - 1] = 2
					queue.append([a, b - 1])
					flag = 1
				if b + 1 < c and hospital[a][b + 1] == 1:
					hospital[a][b + 1] = 2
					queue.append([a, b + 1])
					flag = 1
			if flag:
				cnt += 1
		for i in range(r):
			for j in range(c):
				if hospital[i][j] == 1:
					return -1
		return cnt


class Solution:

	def is_valid(self, i, j, r, c, a):
		if i < 0 or i >= r or j < 0 or (j >= c):
			return False
		return a[i][j] == 1

	def helpaterp(self, a):
		r = len(a)
		c = len(a[0])
		ans = 0
		q = []
		for i in range(r):
			for j in range(c):
				if a[i][j] == 2:
					q.append([i, j])
		while q:
			n = len(q)
			is_affected = False
			for i in range(n):
				p = q.pop(0)
				a[p[0]][p[1]] = 2
				x_pos = [-1, 0, 0, 1]
				y_pos = [0, -1, 1, 0]
				for t in range(len(x_pos)):
					nx = x_pos[t] + p[0]
					ny = y_pos[t] + p[1]
					if self.is_valid(nx, ny, r, c, a):
						q.append([nx, ny])
						is_affected = True
			if is_affected:
				ans += 1
		for i in range(r):
			for j in range(c):
				if a[i][j] == 1:
					return -1
		return ans


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		queue = deque()
		rows = len(hospital)
		cols = len(hospital[0])
		for row in range(rows):
			for col in range(cols):
				if hospital[row][col] == 2:
					queue.append((row, col, 0))
		maxmLevel = 0
		while queue:
			(row, col, level) = queue.popleft()
			maxmLevel = max(maxmLevel, level)
			for (offx, offy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
				neighx = offx + row
				neighy = offy + col
				if 0 <= neighx < rows and 0 <= neighy < cols and (hospital[neighx][neighy] == 1):
					hospital[neighx][neighy] = 2
					queue.append((neighx, neighy, level + 1))
		for row in range(rows):
			for col in range(cols):
				if hospital[row][col] == 1:
					return -1
		return maxmLevel


from collections import deque

class Solution:

	def helpaterp(self, hospital):
		(m, n) = (len(hospital), len(hospital[0]))
		visited = [[-1 for j in range(n)] for i in range(m)]
		que = deque()
		for i in range(m):
			for j in range(n):
				if hospital[i][j] == 2:
					que.append((i, j))
		count = 0
		while que:
			ctr = len(que)
			flag = 0
			while ctr:
				(i, j) = que.popleft()
				if i - 1 >= 0 and hospital[i - 1][j] == 1:
					flag = 1
					hospital[i - 1][j] = 2
					que.append((i - 1, j))
				if i + 1 < m and hospital[i + 1][j] == 1:
					flag = 1
					hospital[i + 1][j] = 2
					que.append((i + 1, j))
				if j - 1 >= 0 and hospital[i][j - 1] == 1:
					flag = 1
					hospital[i][j - 1] = 2
					que.append((i, j - 1))
				if j + 1 < n and hospital[i][j + 1] == 1:
					flag = 1
					hospital[i][j + 1] = 2
					que.append((i, j + 1))
				ctr -= 1
			if flag:
				count += 1
		for i in range(m):
			for j in range(n):
				if hospital[i][j] == 1:
					return -1
		return count


class Solution:

	def helpaterp(self, hospital):
		neg = set()
		pos = set()
		m = len(hospital)
		n = len(hospital[0])
		for i in range(m):
			for j in range(n):
				if hospital[i][j] == 2:
					pos.add((i, j))
				elif hospital[i][j] == 1:
					neg.add((i, j))
		mins = 0
		dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		while len(neg) > 0:
			infected = set()
			for r in pos:
				row = r[0]
				col = r[1]
				for dir in dirs:
					new_row = dir[0] + row
					new_col = dir[1] + col
					if (new_row, new_col) in neg:
						neg.remove((new_row, new_col))
						infected.add((new_row, new_col))
			if len(infected) == 0:
				return -1
			pos = infected
			mins += 1
		return mins