Given a grid of dimension nxm containing 0s and 1s. Find the unit area of the largest region of 1s.
Region of 1's is a group of 1's connected 8-directionally (horizontally, vertically, diagonally).
 
Example 1:
Input: grid = {{1,1,1,0},{0,0,1,0},{0,0,0,1}}
Output: 5
Explanation: The grid is-
1 1 1 0
0 0 1 0
0 0 0 1
The largest region of 1's is colored
in orange.
Example 2:
Input: grid = {{0,1}}
Output: 1
Explanation: The grid is-
0 1
The largest region of 1's is colored in 
orange.
Your Task:
You don't need to read or print anyhting. Your task is to complete the function findMaxArea() which takes grid as input parameter and returns the area of the largest region of 1's.
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)
 
Constraints:
1 ≤ n, m ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: 



class Solution:



    #Function to find unit area of the largest region of 1s.

	def findMaxArea(self, grid):

		#Code here



Solutions:
class Solution:

	def DFS(self, grid, x, y, visited, count, n, m):
		moves = [(-1, -1), (0, -1), (1, -1), (-1, 0), (0, 1), (-1, 1), (1, 0), (1, 1)]
		for (dx, dy) in moves:
			nx = x + dx
			ny = y + dy
			if 0 <= nx < n and 0 <= ny < m and (not visited[nx][ny]) and (grid[nx][ny] == 1):
				visited[nx][ny] = True
				count[0] += 1
				self.DFS(grid, nx, ny, visited, count, n, m)

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = [[False] * m for _ in range(n)]
		maxim = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					count = [1]
					visited[i][j] = True
					self.DFS(grid, i, j, visited, count, n, m)
					if count[0] > maxim:
						maxim = count[0]
		return maxim


class Solution:

	def findMaxArea(self, grid):
		maxArea = 0
		(m, n) = (len(grid), len(grid[0]))

		def dfs(row, col):
			if row < 0 or row >= m or col < 0 or (col >= n):
				return 0
			if grid[row][col] == 1:
				grid[row][col] = 0
				return 1 + dfs(row + 1, col) + dfs(row, col + 1) + dfs(row - 1, col) + dfs(row, col - 1) + dfs(row + 1, col + 1) + dfs(row - 1, col - 1) + dfs(row + 1, col - 1) + dfs(row - 1, col + 1)
			return 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					maxArea = max(maxArea, dfs(i, j))
		return maxArea


class Solution:

	def findMaxArea(self, grid):
		return find_islands(grid)

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

def find_islands(G):

	def visit(G, i, j, visited):
		nonlocal counter
		counter += 1
		visited[i][j] = True
		for neighbour in find_neighbours(i, j, m, n):
			if G[neighbour[0]][neighbour[1]] == 1 and visited[neighbour[0]][neighbour[1]] == False:
				visit(G, neighbour[0], neighbour[1], visited)
	n = len(G)
	m = len(G[0])
	visited = [[False for j in range(m)] for i in range(n)]
	max_counter = 0
	for i in range(n):
		for j in range(m):
			if G[i][j] == 1 and visited[i][j] == False:
				counter = 0
				visit(G, i, j, visited)
				if counter > max_counter:
					max_counter = counter
	return max_counter


class Solution:

	def findMaxArea(self, grid):
		row = len(grid)
		col = len(grid[0])
		direction = [[0, 1], [1, 0], [0, -1], [-1, 0], [1, 1], [-1, -1], [1, -1], [-1, 1]]
		ans = [0]
		queue = []
		vis = [[0 for _ in range(col)] for _ in range(row)]

		def bfs(queue, grid, ans):
			cnt = 1
			while queue:
				(x, y) = queue.pop(0)
				for (i, j) in direction:
					new_x = x + i
					new_y = y + j
					if new_x >= 0 and new_x < row and (new_y >= 0) and (new_y < col) and (vis[new_x][new_y] == 0) and (grid[new_x][new_y] == 1):
						queue.append((new_x, new_y))
						vis[new_x][new_y] = 1
						cnt += 1
			return cnt
		for i in range(row):
			for j in range(col):
				if grid[i][j] == 1 and vis[i][j] == 0:
					queue.append((i, j))
					vis[i][j] = 1
					temp = bfs(queue, grid, ans)
					ans[0] = max(ans[0], temp)
		return ans[0]


class Solution:

	def helper(self, i, j):
		if i < 0 or i >= self.row or j < 0 or (j >= self.col) or (grid[i][j] == 0):
			return 0
		grid[i][j] = 0
		ul = self.helper(i - 1, j - 1)
		u = self.helper(i - 1, j)
		ur = self.helper(i - 1, j + 1)
		l = self.helper(i, j - 1)
		r = self.helper(i, j + 1)
		dl = self.helper(i + 1, j - 1)
		d = self.helper(i + 1, j)
		dr = self.helper(i + 1, j + 1)
		return 1 + ul + u + ur + l + r + dl + d + dr

	def findMaxArea(self, grid):
		(self.row, self.col) = (len(grid), len(grid[0]))
		area = 0
		for i in range(self.row):
			for j in range(self.col):
				if grid[i][j]:
					area = max(area, self.helper(i, j))
		return area


def dfs(r, c, visit, grid, area, n, m):
	visit[r][c] = 1
	area = 1
	l = [[-1, 0], [1, 0], [0, 1], [0, -1], [-1, -1], [1, 1], [-1, 1], [1, -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) and (not visit[nr][nc]):
			area += dfs(nr, nc, visit, grid, area, n, m)
	return area

class Solution:

	def findMaxArea(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		visit = [[0] * m for _ in range(n)]
		area = 0
		maxi = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and (not visit[i][j]):
					maxi = max(maxi, dfs(i, j, visit, grid, area, n, m))
		return maxi


class Solution:

	def findMaxArea(self, grid):
		s = set()

		def dfs(m, n):
			if m >= len(grid) or n >= len(grid[0]) or m < 0 or (n < 0):
				return 0
			if (m, n) in s:
				return 0
			if grid[m][n] == 0:
				return 0
			s.add((m, n))
			size = 1
			size += dfs(m + 1, n)
			size += dfs(m - 1, n)
			size += dfs(m, n + 1)
			size += dfs(m, n - 1)
			size += dfs(m + 1, n + 1)
			size += dfs(m - 1, n - 1)
			size += dfs(m - 1, n + 1)
			size += dfs(m + 1, n - 1)
			return size
		mx = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				mx = max(mx, dfs(i, j))
		return mx


class Solution:

	def findMaxArea(self, grid):
		(m, n) = (len(grid), len(grid[0]))

		def dfs(i, j):
			if i < 0 or i >= m or j < 0 or (j >= n) or (grid[i][j] != 1):
				return
			grid[i][j] = '#'
			count[0] += 1
			for (x, y) in ((-1, 0), (1, 0), (0, -1), (0, 1), (1, 1), (-1, -1), (-1, 1), (1, -1)):
				dfs(i + x, j + y)
		ans = 0
		for i in range(m):
			for j in range(n):
				count = [0]
				if grid[i][j] == 1:
					dfs(i, j)
					ans = max(count[0], ans)
		return ans


from collections import deque

class Solution:

	def findMaxArea(self, grid):
		m = len(grid)
		n = len(grid[0])
		q = deque()
		max_count = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					count = 0
					q.append([i, j])
					while len(q) != 0:
						id = q.popleft()
						idx = id[0]
						idy = id[1]
						count += 1
						grid[idx][idy] = 0
						if idx - 1 >= 0 and grid[idx - 1][idy] == 1:
							grid[idx - 1][idy] = 0
							q.append([idx - 1, idy])
						if idy - 1 >= 0 and grid[idx][idy - 1] == 1:
							grid[idx][idy - 1] = 0
							q.append([idx, idy - 1])
						if idx + 1 < m and grid[idx + 1][idy] == 1:
							grid[idx + 1][idy] = 0
							q.append([idx + 1, idy])
						if idy + 1 < n and grid[idx][idy + 1] == 1:
							grid[idx][idy + 1] = 0
							q.append([idx, idy + 1])
						if idx - 1 >= 0 and idy - 1 >= 0 and (grid[idx - 1][idy - 1] == 1):
							grid[idx - 1][idy - 1] = 0
							q.append([idx - 1, idy - 1])
						if idx + 1 < m and idy + 1 < n and (grid[idx + 1][idy + 1] == 1):
							grid[idx + 1][idy + 1] = 0
							q.append([idx + 1, idy + 1])
						if idx - 1 >= 0 and idy + 1 < n and (grid[idx - 1][idy + 1] == 1):
							grid[idx - 1][idy + 1] = 0
							q.append([idx - 1, idy + 1])
						if idx + 1 < m and idy - 1 >= 0 and (grid[idx + 1][idy - 1] == 1):
							grid[idx + 1][idy - 1] = 0
							q.append([idx + 1, idy - 1])
					max_count = max(count, max_count)
		return max_count


class Solution:

	def findMaxArea(self, grid):
		(ROWS, COLS) = (len(grid), len(grid[0]))
		visit = set()

		def dfs(r, c):
			if r < 0 or r == ROWS or c < 0 or (c == COLS) or (grid[r][c] == 0) or ((r, c) in visit):
				return 0
			visit.add((r, c))
			return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1) + dfs(r - 1, c - 1) + dfs(r - 1, c + 1) + dfs(r + 1, c - 1) + dfs(r + 1, c + 1)
		area = 0
		for r in range(ROWS):
			for c in range(COLS):
				area = max(area, dfs(r, c))
		return area


class Solution:

	def __init__(self):
		self.val = 0
		self.res = 0

	def check(self, x, y, r, c, grid):
		if 0 <= x < r and 0 <= y < c:
			if grid[x][y] == 1:
				return True
		return False

	def explore(self, grid, dis_x, dis_y, visited, pos):
		if pos not in visited:
			visited.add(pos)
			self.val += 1
			for i in range(8):
				(new_x, new_y) = (pos[0] + dis_x[i], pos[1] + dis_y[i])
				if self.check(new_x, new_y, len(grid), len(grid[0]), grid):
					self.explore(grid, dis_x, dis_y, visited, tuple([new_x, new_y]))
		return self.val

	def findMaxArea(self, grid):
		dis_x = [1, 1, -1, -1, 0, 0, 1, -1]
		dis_y = [-1, 1, -1, 1, 1, -1, 0, 0]
		visited = set()
		res = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					if tuple([i, j]) not in visited:
						self.val = 0
						a = self.explore(grid, dis_x, dis_y, visited, tuple([i, j]))
						self.res = max(self.val, self.res)
		return self.res


def dfs(i, j, visited, grid, cnt):
	if i < 0 or i >= len(grid) or j < 0 or (j >= len(grid[0])) or (visited[i][j] == 1) or (grid[i][j] == 0):
		return
	temp = max(temp, cnt)
	visited[i][j] = 1
	dx = [-1, 0, 1, 0, 1, 1, -1, -1]
	dy = [0, 1, 0, -1, 1, -1, 1, -1]
	for k in range(8):
		dfs(i + dx[k], j + dy[k], visited, grid, cnt + 1)
	print(cnt)

class Solution:
	temp = 0
	cnt = 1

	def findMaxArea(self, grid):
		(N, M) = (len(grid), len(grid[0]))
		visited = [[0 for _ in range(M)] for _ in range(N)]
		ans = 0
		for i in range(N):
			for j in range(M):
				if visited[i][j] == 0 and grid[i][j] == 1:
					visited[i][j] = 1
					Solution.cnt = 1
					Solution.temp = 0
					self.dfs(i, j, visited, grid)
					ans = max(ans, Solution.temp)
		return ans

	def dfs(self, i, j, visited, grid):
		Solution.temp = max(Solution.temp, Solution.cnt)
		dx = [-1, 0, 1, 0, 1, 1, -1, -1]
		dy = [0, 1, 0, -1, 1, -1, 1, -1]
		for k in range(8):
			n_i = i + dx[k]
			n_j = j + dy[k]
			if n_i >= 0 and n_i < len(grid) and (n_j >= 0) and (n_j < len(grid[0])) and (visited[n_i][n_j] == 0) and (grid[n_i][n_j] == 1):
				Solution.cnt += 1
				visited[n_i][n_j] = Solution.cnt
				self.dfs(n_i, n_j, visited, grid)
		Solution.temp = max(Solution.temp, Solution.cnt)


class Solution:

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		ans = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					count = self.count(i, j, grid, n, m)
					ans = max(count, ans)
		return ans

	def count(self, row, col, A, n, m):
		if any([row < 0, col < 0, row >= n, col >= m]):
			return 0
		if A[row][col] == 0:
			return 0
		count = 1
		A[row][col] = 0
		for r in range(row - 1, row + 2):
			for c in range(col - 1, col + 2):
				count += self.count(r, c, A, n, m)
		return count


class Solution:

	def findMaxArea(self, grid):
		(ROWS, COLS) = (len(grid), len(grid[0]))

		def dfs(i, j):
			if i < 0 or i == ROWS or j < 0 or (j == COLS) or (grid[i][j] != 1):
				return 0
			grid[i][j] = 0
			return 1 + dfs(i, j - 1) + dfs(i, j + 1) + dfs(i - 1, j) + dfs(i - 1, j + 1) + dfs(i - 1, j - 1) + dfs(i + 1, j) + dfs(i + 1, j - 1) + dfs(i + 1, j + 1)
		res = 0
		for i in range(ROWS):
			for j in range(COLS):
				if grid[i][j] == 1:
					res = max(res, dfs(i, j))
		return res


class Solution:

	def findMaxArea(self, grid):
		res = 0
		(r, c) = (len(grid), len(grid[0]))

		def check(i, j):
			if i < r and i >= 0 and (j < c) and (j >= 0) and (grid[i][j] == 1):
				return True
			return False

		def f(m, n):
			s = [[m, n]]
			p = 0
			while len(s) != 0:
				(i, j) = s.pop(0)
				p += 1
				if check(i + 1, j):
					grid[i + 1][j] = 0
					s.append([i + 1, j])
				if check(i - 1, j):
					grid[i - 1][j] = 0
					s.append([i - 1, j])
				if check(i, j + 1):
					grid[i][j + 1] = 0
					s.append([i, j + 1])
				if check(i, j - 1):
					grid[i][j - 1] = 0
					s.append([i, j - 1])
				if check(i - 1, j - 1):
					grid[i - 1][j - 1] = 0
					s.append([i - 1, j - 1])
				if check(i + 1, j + 1):
					grid[i + 1][j + 1] = 0
					s.append([i + 1, j + 1])
				if check(i - 1, j + 1):
					grid[i - 1][j + 1] = 0
					s.append([i - 1, j + 1])
				if check(i + 1, j - 1):
					grid[i + 1][j - 1] = 0
					s.append([i + 1, j - 1])
			return p
		for i in range(r):
			for j in range(c):
				if grid[i][j] == 1:
					grid[i][j] = 0
					res = max(res, f(i, j))
		return res


class Solution:

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

		def helper(r, c):
			if r < 0 or c < 0 or r >= row or (c >= col) or (visited[r][c] == True) or (grid[r][c] == 0):
				return 0
			visited[r][c] = True
			ans = 1
			for dx in range(-1, 2):
				for dy in range(-1, 2):
					x = r + dx
					y = c + dy
					ans += helper(x, y)
			return ans
		res = 0
		for i in range(row):
			for j in range(col):
				res = max(res, helper(i, j))
		return res


class Solution:

	def isSafe(self, grid, row, col, visited):
		return row >= 0 and row < len(grid) and (col >= 0) and (col < len(grid[0])) and (grid[row][col] == 1) and (not visited[row][col])

	def dfscount(self, grid, row, col, visited):
		rowNbr = [-1, -1, -1, 0, 0, 1, 1, 1]
		colNbr = [-1, 0, 1, -1, 1, -1, 0, 1]
		visited[row][col] = True
		count = 1
		for k in range(8):
			if self.isSafe(grid, row + rowNbr[k], col + colNbr[k], visited):
				count += self.dfscount(grid, row + rowNbr[k], col + colNbr[k], visited)
		return count

	def findMaxArea(self, grid):
		visited = [[False for j in range(len(grid[0]))] for i in range(len(grid))]
		max1 = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1 and (not visited[i][j]):
					count = self.dfscount(grid, i, j, visited)
					if count > max1:
						max1 = count
		return max1


class Solution:

	def findMaxArea(self, grid):
		di = [1, 1, 1, 0, 0, -1, -1, -1]
		dj = [1, 0, -1, 1, -1, 1, 0, -1]
		visited = set()

		def dfs(i, j):
			visited.add((i, j))
			area = 1
			for d in range(8):
				newi = di[d] + i
				newj = dj[d] + j
				if not (0 <= newi < len(grid) and 0 <= newj < len(grid[0])):
					continue
				if (newi, newj) in visited or grid[newi][newj] == 0:
					continue
				area += dfs(newi, newj)
			return area
		bestArea = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if (i, j) in visited or grid[i][j] == 0:
					continue
				bestArea = max(bestArea, dfs(i, j))
		return bestArea


class Solution:

	def findMaxArea(self, grid):
		(m, n) = (len(grid), len(grid[0]))
		visited = [[0] * n for o in range(m)]
		result = 0
		for i in range(m):
			for j in range(n):
				if self.tovisit(grid, m, n, i, j, visited):
					count = 1
					count = self.BFS(grid, m, n, i, j, visited, count)
					result = max(count, result)
		return result

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

	def DFS(self, grid, m, n, i, j, visited, count):
		row = [-1, -1, -1, 0, 0, 1, 1, 1]
		columns = [-1, 0, 1, -1, 1, -1, 0, 1]
		visited[i][j] = 1
		for k in range(8):
			if self.tovisit(grid, m, n, i + row[k], j + columns[k], visited):
				count += 1
				count = self.DFS(grid, m, n, i + row[k], j + columns[k], visited, count)
		return count

	def BFS(self, grid, m, n, i, j, visited, count):
		row = [-1, -1, -1, 0, 0, 1, 1, 1]
		columns = [-1, 0, 1, -1, 1, -1, 0, 1]
		visited[i][j] = 1
		queue = []
		queue.append((i, j))
		while queue:
			queue = [x for x in queue if x != []]
			s = queue.pop(0)
			i = s[0]
			j = s[1]
			for k in range(8):
				if self.tovisit(grid, m, n, i + row[k], j + columns[k], visited):
					count += 1
					visited[i + row[k]][j + columns[k]] = 1
					queue.append((i + row[k], j + columns[k]))
		return count


class Solution:

	def findMaxArea(self, grid):
		(m, n) = (len(grid), len(grid[0]))
		visited = [[0] * n for o in range(m)]
		result = 0
		for i in range(m):
			for j in range(n):
				if self.tovisit(grid, m, n, i, j, visited):
					count = 1
					count = self.DFS(grid, m, n, i, j, visited, count)
					result = max(count, result)
		return result

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

	def DFS(self, grid, m, n, i, j, visited, count):
		row = [-1, -1, -1, 0, 0, 1, 1, 1]
		columns = [-1, 0, 1, -1, 1, -1, 0, 1]
		visited[i][j] = 1
		for k in range(8):
			if self.tovisit(grid, m, n, i + row[k], j + columns[k], visited):
				count += 1
				count = self.DFS(grid, m, n, i + row[k], j + columns[k], visited, count)
		return count


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

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

		def helper(r, c):
			if r < 0 or r >= row or c < 0 or (c >= col) or (grid[r][c] == 0) or (visited[r][c] == True):
				return 0
			directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (1, -1), (-1, -1)]
			visited[r][c] = True
			ans = 1
			for i in range(-1, 2):
				for j in range(-1, 2):
					if i == 0 and j == 0:
						continue
					nr = r + i
					nc = c + j
					ans += helper(nr, nc)
			return ans
		res = 0
		for i in range(row):
			for j in range(col):
				res = max(res, helper(i, j))
		return res


class Solution:

	def findMaxArea(self, grid):
		(m, n) = (len(grid), len(grid[0]))
		visited = [[0] * n for i in range(m)]
		result = 0
		for i in range(m):
			for j in range(n):
				if self.isYetToVisit(grid, i, j, m, n, visited):
					count = 1
					count = self.DFS(grid, i, j, m, n, visited, count)
					result = max(result, count)
		return result

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

	def DFS(self, grid, i, j, m, n, visited, count):
		rowNumbers = [-1, -1, -1, 0, 0, 1, 1, 1]
		colNumbers = [-1, 0, 1, -1, 1, -1, 0, 1]
		visited[i][j] = 1
		for k in range(8):
			if self.isYetToVisit(grid, i + rowNumbers[k], j + colNumbers[k], m, n, visited):
				count += 1
				count = self.DFS(grid, i + rowNumbers[k], j + colNumbers[k], m, n, visited, count)
		return count


class Solution:

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = [[0 for j in range(m)] for i in range(n)]
		area = 0
		for i in range(n):
			for j in range(m):
				if not visited[i][j] and grid[i][j] == 1:
					c = self.dfs(i, j, visited)
					if c > area:
						area = c
		return area

	def isvalid(self, i, j, visited):
		if 0 <= i < n and 0 <= j < m and (not visited[i][j]) and grid[i][j]:
			return True
		else:
			return False

	def dfs(self, i, j, visited):
		visited[i][j] = 1
		r = [1, -1, 0, 0, 1, -1, -1, 1]
		c = [0, 0, 1, -1, 1, 1, -1, -1]
		ans = 0
		for k in range(8):
			if self.isvalid(i + r[k], j + c[k], visited):
				x = self.dfs(i + r[k], j + c[k], visited)
				ans += x
		return ans + 1


class disjointSet:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.size = [1 for i in range(n)]

	def findParent(self, node):
		if node != self.parent[node]:
			self.parent[node] = self.findParent(self.parent[node])
		return self.parent[node]

	def unionBySize(self, u, v):
		pu = self.findParent(u)
		pv = self.findParent(v)
		if pu == pv:
			return
		if self.size[pv] > self.size[pu]:
			self.parent[pu] = pv
			self.size[pv] += self.size[pu]
		else:
			self.parent[pv] = pu
			self.size[pu] += self.size[pv]

class Solution:

	def isValid(self, row, col, n, m):
		if row < n and col < m and (row >= 0) and (col >= 0):
			return True
		return False

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		flag = 0
		visited = [[0 for i in range(m)] for j in range(n)]
		ds = disjointSet(n * m)
		dr = [-1, 0, 1, 0, -1, -1, 1, 1]
		dc = [0, -1, 0, 1, -1, 1, -1, 1]
		for row in range(n):
			for col in range(m):
				if visited[row][col] == 0 and grid[row][col] == 1:
					flag = 1
					nodeNo = row * m + col
					visited[row][col] = 1
					for i in range(8):
						adrow = row + dr[i]
						adcol = col + dc[i]
						if self.isValid(adrow, adcol, n, m) and grid[adrow][adcol] == 1:
							adNodeNo = adrow * m + adcol
							ds.unionBySize(adNodeNo, nodeNo)
		if flag == 0:
			return 0
		ans = max(ds.size)
		return ans


class Solution:

	def findMaxArea(self, grid):

		def bfs(grid, row, col, n, m, li):
			ans = 1
			que = [[row, col]]
			grid[row][col] = '#'
			while que:
				(row1, col1) = que.pop(0)
				dirow = [-1, -1, 0, 1, 1, 1, 0, -1]
				dicol = [0, 1, 1, 1, 0, -1, -1, -1]
				for j in range(8):
					nrow = row1 + dirow[j]
					ncol = col1 + dicol[j]
					if nrow >= 0 and ncol >= 0 and (nrow < n) and (ncol < m) and (grid[nrow][ncol] == 1):
						grid[nrow][ncol] = '#'
						ans += 1
						que.append([nrow, ncol])
			return ans
		n = len(grid)
		m = len(grid[0])
		maxi = -10 ** 9
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					kk = bfs(grid, i, j, n, m, 0)
					maxi = max(kk, maxi)
		if maxi == -10 ** 9:
			return 0
		return maxi


class DisjointSet:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.size = [1] * n

	def find(self, x):
		if self.parent[x] == x:
			return x
		self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		ul_x = self.find(x)
		ul_y = self.find(y)
		if ul_x == ul_y:
			return 0
		if self.size[ul_x] >= self.size[ul_y]:
			self.size[ul_x] += self.size[ul_y]
			self.parent[ul_y] = ul_x
		else:
			self.size[ul_y] += self.size[ul_x]
			self.parent[ul_x] = ul_y
		return 1

class Solution:

	def findMaxArea(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		visited = [[0] * m for _ in range(n)]

		def dfs(i, j):
			visited[i][j] = 1
			size = 1
			for delRow in range(-1, 2):
				for delCol in range(-1, 2):
					nr = delRow + i
					nc = delCol + j
					if nr >= 0 and nr < n and (nc >= 0) and (nc < m) and (grid[nr][nc] == 1) and (not visited[nr][nc]):
						size += dfs(nr, nc)
			return size
		maxi = 0
		for i in range(n):
			for j in range(m):
				if not visited[i][j] and grid[i][j]:
					maxi = max(maxi, dfs(i, j))
		return maxi


class Solution:

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		level = 0
		counts = [0]
		while level < n:
			if 1 in grid[level]:
				stack = [(level, grid[level].index(1))]
				counts.append(0)
				while stack:
					(i, j) = stack.pop()
					counts[-1] += grid[i][j]
					grid[i][j] = 0
					if i > 0 and grid[i - 1][j]:
						stack.append((i - 1, j))
					if i < n - 1 and grid[i + 1][j]:
						stack.append((i + 1, j))
					if j > 0 and grid[i][j - 1]:
						stack.append((i, j - 1))
					if j < m - 1 and grid[i][j + 1]:
						stack.append((i, j + 1))
					if i > 0 and j > 0 and grid[i - 1][j - 1]:
						stack.append((i - 1, j - 1))
					if i > 0 and j < m - 1 and grid[i - 1][j + 1]:
						stack.append((i - 1, j + 1))
					if i < n - 1 and j > 0 and grid[i + 1][j - 1]:
						stack.append((i + 1, j - 1))
					if i < n - 1 and j < m - 1 and grid[i + 1][j + 1]:
						stack.append((i + 1, j + 1))
			else:
				level += 1
		return max(counts)


from collections import deque

class Solution:

	def findMaxArea(self, grid):
		ans = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					ans = max(ans, self.bfs(grid, i, j))
		return ans

	def bfs(self, grid, i, j):
		count = 0
		x = deque()
		x.append([i, j])
		grid[i][j] = 0
		while x:
			(ix, iy) = x.popleft()
			count += 1
			for (dx, dy) in [[0, 1], [1, 0], [-1, 0], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]:
				nr = ix + dx
				nc = iy + dy
				if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and (grid[nr][nc] == 1):
					grid[nr][nc] = 0
					x.append([nr, nc])
		return count


class DisjointSet:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.size = [1 for i in range(n)]

	def findUParent(self, node):
		if node == self.parent[node]:
			return node
		self.parent[node] = self.findUParent(self.parent[node])
		return self.parent[node]

	def unionBySize(self, u, v):
		pu = self.findUParent(u)
		pv = self.findUParent(v)
		if pu == pv:
			return
		if self.size[pu] < self.size[pv]:
			self.size[pv] += self.size[pu]
			self.parent[pu] = pv
		else:
			self.size[pu] += self.size[pv]
			self.parent[pv] = pu

class Solution:

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		d = DisjointSet(n * m)
		dx = [1, 0, 0, -1, -1, -1, 1, 1]
		dy = [0, -1, 1, 0, -1, 1, -1, 1]
		c_zero = True
		for i in range(n):
			for j in range(m):
				node = i * m + j
				if grid[i][j] == 1:
					c_zero = False
					for r in range(8):
						x = i + dx[r]
						y = j + dy[r]
						if x >= 0 and x < n and (y >= 0) and (y < m) and (grid[x][y] == 1):
							newnode = x * m + y
							if d.findUParent(node) != d.findUParent(newnode):
								d.unionBySize(node, newnode)
		if c_zero:
			return 0
		return max(d.size)


class Solution:

	def findMaxArea(self, arr):

		def dfs_helper(arr, i, j, visited, c):
			if i < 0 or j < 0 or i >= n or (j >= m) or (arr[i][j] == 0) or (visited[i][j] == True):
				return
			visited[i][j] = True
			c[0] += 1
			dfs_helper(arr, i + 1, j, visited, c)
			dfs_helper(arr, i - 1, j, visited, c)
			dfs_helper(arr, i, j + 1, visited, c)
			dfs_helper(arr, i, j - 1, visited, c)
			dfs_helper(arr, i - 1, j - 1, visited, c)
			dfs_helper(arr, i - 1, j + 1, visited, c)
			dfs_helper(arr, i + 1, j - 1, visited, c)
			dfs_helper(arr, i + 1, j + 1, visited, c)

		def island(arr, n, m):
			visited = [[False for i in range(m)] for j in range(n)]
			ans = 0
			for i in range(n):
				for j in range(m):
					if arr[i][j] == 1 and visited[i][j] == False:
						c = [0]
						dfs_helper(arr, i, j, visited, c)
						ans = max(ans, c[0])
			return ans
		n = len(arr)
		m = len(arr[0])
		return island(arr, n, m)


from collections import deque

def bfs(grid, r, c, n, m, res):
	rl = [-1, -1, -1, 0, 0, 1, 1, 1]
	cl = [-1, 0, 1, -1, 1, -1, 0, 1]
	res += 1
	grid[r][c] = 0
	q = deque()
	q.append([r, c])
	while len(q) > 0:
		temp = q.popleft()
		row = temp[0]
		col = temp[1]
		for i in range(8):
			newrow = row + rl[i]
			newcol = col + cl[i]
			if newrow >= 0 and newrow < n and (newcol >= 0) and (newcol < m):
				if grid[newrow][newcol] == 1:
					res += 1
					grid[newrow][newcol] = 0
					q.append([newrow, newcol])
	return res

class Solution:

	def findMaxArea(self, grid):
		maxi = 0
		n = len(grid)
		m = len(grid[0])
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					res = 0
					a = bfs(grid, i, j, n, m, res)
					maxi = max(maxi, a)
		return maxi


class Solution:

	def __init__(self):
		self.visited = {}

	def bfs(self, a, a1):
		queue = [a]
		c = 0
		self.visited[a] = 1
		while len(queue) > 0:
			x = queue.pop(0)
			c += 1
			for i in a1[x]:
				if i not in self.visited:
					self.visited[i] = 1
					queue.append(i)
		return c

	def findMaxArea(self, a):
		a1 = {}
		for i in range(len(a)):
			for j in range(len(a[i])):
				if a[i][j] == 1:
					g = str(i) + ' ' + str(j)
					a1[g] = []
					o = [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1], [i + 1, j + 1], [i - 1, j - 1], [i + 1, j - 1], [i - 1, j + 1]]
					for k in o:
						if k[0] >= 0 and k[0] < len(a) and (k[1] >= 0) and (k[1] < len(a[0])) and (a[k[0]][k[1]] == 1):
							h = str(k[0]) + ' ' + str(k[1])
							a1[g].append(h)
		res = 0
		for i in a1:
			if i not in self.visited:
				res = max(res, self.bfs(i, a1))
		return res


class Solution:

	def findMaxArea(self, grid):
		ma = 0
		for i in range(0, len(grid)):
			for j in range(0, len(grid[0])):
				temp = 1
				if grid[i][j] == 1:
					temp = self.traverse(grid, i, j, temp)
					if temp > ma:
						ma = temp
		return ma

	def traverse(self, grid, i, j, temp):
		if grid[i][j] == 1:
			grid[i][j] = 0
			if i - 1 >= 0:
				if grid[i - 1][j] == 1:
					temp += 1
					temp = self.traverse(grid, i - 1, j, temp)
				if j - 1 >= 0:
					if grid[i - 1][j - 1] == 1:
						temp += 1
						temp = self.traverse(grid, i - 1, j - 1, temp)
				if j + 1 < len(grid[0]):
					if grid[i - 1][j + 1] == 1:
						temp += 1
						temp = self.traverse(grid, i - 1, j + 1, temp)
			if j - 1 >= 0:
				if grid[i][j - 1] == 1:
					temp += 1
					temp = self.traverse(grid, i, j - 1, temp)
			if j + 1 < len(grid[0]):
				if grid[i][j + 1] == 1:
					temp += 1
					temp = self.traverse(grid, i, j + 1, temp)
			if i + 1 < len(grid):
				if grid[i + 1][j] == 1:
					temp += 1
					temp = self.traverse(grid, i + 1, j, temp)
				if j - 1 >= 0:
					if grid[i + 1][j - 1] == 1:
						temp += 1
						temp = self.traverse(grid, i + 1, j - 1, temp)
				if j + 1 < len(grid[0]):
					if grid[i + 1][j + 1] == 1:
						temp += 1
						temp = self.traverse(grid, i + 1, j + 1, temp)
		return temp


from collections import deque

class Solution:

	def findMaxArea(self, grid):
		(self.row, self.col) = (len(grid), len(grid[0]))
		area = 0
		for i in range(self.row):
			for j in range(self.col):
				if grid[i][j]:
					area = max(area, self.helper(i, j))
		return area

	def helper(self, i, j):
		if i < 0 or i >= self.row or j < 0 or (j >= self.col) or (grid[i][j] == 0):
			return 0
		grid[i][j] = 0
		leftup = self.helper(i - 1, j - 1)
		up = self.helper(i - 1, j)
		rightup = self.helper(i - 1, j + 1)
		left = self.helper(i, j - 1)
		right = self.helper(i, j + 1)
		leftdown = self.helper(i + 1, j - 1)
		down = self.helper(i + 1, j)
		rightdown = self.helper(i + 1, j + 1)
		return 1 + leftup + up + rightup + left + right + leftdown + down + rightdown


import sys

class Solution:

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

	def dfs(self, x, y, grid, visited, moves):
		visited[x][y] = True
		ans = 0
		for move in moves:
			nx = x + move[0]
			ny = y + move[1]
			if not self.isValid(nx, ny, len(grid), len(grid[0])):
				continue
			if visited[nx][ny]:
				continue
			if grid[nx][ny] == 1:
				ans += self.dfs(nx, ny, grid, visited, moves)
		return ans + 1

	def findMaxArea(self, grid):
		sys.setrecursionlimit(10 ** 6)
		r = len(grid)
		c = len(grid[0])
		moves = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
		visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
		ans = 0
		for i in range(r):
			for j in range(c):
				if not visited[i][j] and grid[i][j] == 1:
					ans = max(ans, self.dfs(i, j, grid, visited, moves))
		return ans


arr = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [-1, -1], [-1, 1], [1, -1]]

class Solution:

	def findMaxArea(self, grid):
		output = 0
		m = len(grid)
		n = len(grid[0])
		visited = [[grid[j][i] == 0 for i in range(n)] for j in range(m)]
		for i in range(m):
			for j in range(n):
				if visited[i][j] == False:
					count = self.helper(i, j, visited)
					if output < count:
						output = count
		return output

	def helper(self, i, j, visited):
		if i >= 0 and i < len(visited) and (j >= 0) and (j < len(visited[0])) and (not visited[i][j]):
			visited[i][j] = True
			summ = 1
			for k in arr:
				summ += self.helper(i + k[0], j + k[1], visited)
			return summ
		return 0


class Solution:

	def findMaxArea(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		moves = [[-1, 0], [1, 0], [0, 1], [0, -1], [1, 1], [-1, -1], [1, -1], [-1, 1]]

		def dfs(x, y):
			grid[x][y] = -1
			ans = 1
			for (i, j) in moves:
				nx = x + i
				ny = y + j
				if nx >= 0 and nx < n and (ny >= 0) and (ny < m) and (grid[nx][ny] == 1):
					ans += dfs(nx, ny)
			return ans
		maxarea = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					maxarea = max(maxarea, dfs(i, j))
		return maxarea


def dfs(graph, x, y, visited):
	if x < 0 or y < 0 or x >= len(graph) or (y >= len(graph[0])) or visited[x][y] or (not graph[x][y]):
		return 0
	visited[x][y] = True
	return 1 + dfs(graph, x - 1, y, visited) + dfs(graph, x + 1, y, visited) + dfs(graph, x, y - 1, visited) + dfs(graph, x, y + 1, visited) + dfs(graph, x - 1, y - 1, visited) + dfs(graph, x - 1, y + 1, visited) + dfs(graph, x + 1, y - 1, visited) + dfs(graph, x + 1, y + 1, visited)

class Solution:

	def findMaxArea(self, grid):
		ans = 0
		visited = [[0] * len(grid[0]) for i in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if not visited[i][j] and grid[i][j]:
					ans = max(ans, dfs(grid, i, j, visited))
		return ans


class Solution:

	def findMaxArea(self, grid):
		m = len(grid)
		n = len(grid[0])
		output = 0
		visited = [[False for i in range(n)] for j in range(m)]
		for i in range(m):
			for j in range(n):
				if not grid[i][j]:
					visited[i][j] = True
		for i in range(m):
			for j in range(n):
				if not visited[i][j]:
					output = max(output, self.dfs(i, j, m, n, visited))
		return output

	def dfs(self, i, j, m, n, visited):
		if not (i >= 0 and i < m and (j >= 0) and (j < n)) or visited[i][j]:
			return 0
		visited[i][j] = True
		return 1 + self.dfs(i + 1, j, m, n, visited) + self.dfs(i - 1, j, m, n, visited) + self.dfs(i, j + 1, m, n, visited) + self.dfs(i, j - 1, m, n, visited) + self.dfs(i + 1, j + 1, m, n, visited) + self.dfs(i - 1, j - 1, m, n, visited) + self.dfs(i - 1, j + 1, m, n, visited) + self.dfs(i + 1, j - 1, m, n, visited)


from collections import deque

class Solution:

	def findMaxArea(self, grid):
		moves = []
		for i in [-1, 0, 1]:
			for j in [-1, 0, 1]:
				moves.append((i, j))
		visited = set()
		(n, m) = (len(grid), len(grid[0]))
		valid = lambda i, j: 0 <= i < n and 0 <= j < m and (grid[i][j] == 1) and ((i, j) not in visited)

		def bfs(i, j):
			q = deque([(i, j)])
			size = 0
			visited.add((i, j))
			while q:
				(i, j) = q.popleft()
				size += 1
				for (di, dj) in moves:
					(newi, newj) = (i + di, j + dj)
					if valid(newi, newj):
						q.append((newi, newj))
						visited.add((newi, newj))
			return size
		ans = 0
		for i in range(n):
			for j in range(m):
				if (i, j) not in visited and grid[i][j] == 1:
					ans = max(ans, bfs(i, j))
		return ans


from collections import deque

class Solution:

	def findMaxArea(self, grid):
		max_count = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					max_count = max(max_count, self.compute_area(grid, i, j))
		return max_count

	def compute_area(self, grid, row, col):
		queue = deque()
		queue.append((row, col))
		grid[row][col] = 0
		count = 0
		while queue:
			(qrow, qcol) = queue.popleft()
			count += 1
			for (drow, dcol) in [(0, 1), (1, 0), (-1, 0), (0, -1), (-1, 1), (1, -1), (1, 1), (-1, -1)]:
				(nrow, ncol) = (drow + qrow, dcol + qcol)
				if 0 <= nrow < len(grid) and 0 <= ncol < len(grid[0]) and (grid[nrow][ncol] == 1):
					grid[nrow][ncol] = 0
					queue.append((nrow, ncol))
		return count


class DisjointSet:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.size = [1 for i in range(n)]

	def findUParent(self, node):
		if node == self.parent[node]:
			return node
		self.parent[node] = self.findUParent(self.parent[node])
		return self.parent[node]

	def unionBySize(self, u, v):
		pu = self.findUParent(u)
		pv = self.findUParent(v)
		if pu == pv:
			return
		if self.size[pu] < self.size[pv]:
			self.size[pv] += self.size[pu]
			self.parent[pu] = pv
		else:
			self.size[pu] += self.size[pv]
			self.parent[pv] = pu

class Solution:

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		ds = DisjointSet(n * m)
		dx = [1, 0, 0, -1, -1, -1, 1, 1]
		dy = [0, -1, 1, 0, -1, 1, -1, 1]
		zcount = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					thisNode = i * m + j
					for r in range(8):
						x = i + dx[r]
						y = j + dy[r]
						if x >= 0 and x < n and (y >= 0) and (y < m) and (grid[x][y] == 1):
							neiNode = x * m + y
							ds.unionBySize(thisNode, neiNode)
				else:
					zcount += 1
		if zcount == n * m:
			return 0
		for i in range(n * m):
			ds.findUParent(i)
		max_ = -1
		for i in range(n * m):
			max_ = max(max_, ds.size[i])
		return max_


import sys
sys.setrecursionlimit(10 ** 9)

def visit(a, i, j, visited, n, m, ans):
	visited[i][j] = True
	ans[0] = ans[0] + 1
	if i - 1 >= 0 and j - 1 >= 0 and (a[i - 1][j - 1] == 1) and (visited[i - 1][j - 1] == False):
		visit(a, i - 1, j - 1, visited, n, m, ans)
	if i - 1 >= 0 and j + 1 < m and (a[i - 1][j + 1] == 1) and (visited[i - 1][j + 1] == False):
		visit(a, i - 1, j + 1, visited, n, m, ans)
	if i - 1 >= 0 and a[i - 1][j] == 1 and (visited[i - 1][j] == False):
		visit(a, i - 1, j, visited, n, m, ans)
	if j - 1 >= 0 and a[i][j - 1] == 1 and (visited[i][j - 1] == False):
		visit(a, i, j - 1, visited, n, m, ans)
	if j + 1 < m and a[i][j + 1] == 1 and (visited[i][j + 1] == False):
		visit(a, i, j + 1, visited, n, m, ans)
	if i + 1 < n and j - 1 >= 0 and (a[i + 1][j - 1] == 1) and (visited[i + 1][j - 1] == False):
		visit(a, i + 1, j - 1, visited, n, m, ans)
	if i + 1 < n and j + 1 < m and (a[i + 1][j + 1] == 1) and (visited[i + 1][j + 1] == False):
		visit(a, i + 1, j + 1, visited, n, m, ans)
	if i + 1 < n and a[i + 1][j] == 1 and (visited[i + 1][j] == False):
		visit(a, i + 1, j, visited, n, m, ans)

class Solution:

	def findMaxArea(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		visited = [[False] * m for i in range(n)]
		cc = 0
		ans = [0]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and visited[i][j] == False:
					visit(grid, i, j, visited, n, m, ans)
					cc = max(cc, ans[0])
					ans = [0]
		return cc


class Solution:

	def findMaxArea(self, grid):

		def fun(i, j):
			if i < 0 or i > row - 1 or j < 0 or (j > col - 1):
				return 0
			if grid[i][j] == 0:
				return 0
			c = 1
			grid[i][j] = 0
			for a in range(i - 1, i + 2, 1):
				for b in range(j - 1, j + 2, 1):
					c += fun(a, b)
			return c
		row = len(grid)
		col = len(grid[0])
		x = []
		for i in range(row):
			for j in range(col):
				if grid[i][j] == 1:
					x.append(fun(i, j))
		return max(x) if x else 0


class Solution:

	def dfs(self, i, j, grid):
		if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])):
			return 0
		if grid[i][j] == 0:
			return 0
		grid[i][j] = 0
		count = 1
		for a in range(i - 1, i + 2, 1):
			for b in range(j - 1, j + 2, 1):
				count += self.dfs(a, b, grid)
		return count

	def findMaxArea(self, grid):
		m = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					m = max(m, self.dfs(i, j, grid))
		return m


class Solution:

	def findMaxArea(self, grid):
		(n, m) = (len(grid), len(grid[0]))

		def DFS(i, j, c):
			if i < 0 or i >= n or j < 0 or (j >= m) or (grid[i][j] != 1):
				return
			c[0] += 1
			grid[i][j] = 0
			DFS(i - 1, j - 1, c)
			DFS(i - 1, j, c)
			DFS(i - 1, j + 1, c)
			DFS(i, j - 1, c)
			DFS(i, j + 1, c)
			DFS(i + 1, j - 1, c)
			DFS(i + 1, j, c)
			DFS(i + 1, j + 1, c)
		res = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					c = [0]
					DFS(i, j, c)
					res = max(res, c[0])
		return res


class Solution:

	def findMaxArea(self, grid):

		def dfs(i, j, r, c):
			if i < 0 or j < 0 or i >= r or (j >= c) or (grid[i][j] == 0):
				return 0
			grid[i][j] = 0
			cnt = 1
			directions = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
			for (ki, kj) in directions:
				(_i, _j) = (i + ki, j + kj)
				cnt += dfs(_i, _j, r, c)
			return cnt
		(r, c) = (len(grid), len(grid[0]))
		maxArea = 0
		for i in range(r):
			for j in range(c):
				if grid[i][j] == 1:
					maxArea = max(maxArea, dfs(i, j, r, c))
		return maxArea


from collections import deque

class Solution:

	def BFS(self, i, j, rows, cols, visited, grid, temp):
		queue = deque()
		dx = [0, 0, 1, 1, 1, -1, -1, -1]
		dy = [1, -1, 0, 1, -1, 0, 1, -1]
		queue.append((i, j))
		visited[i][j] = True
		while queue:
			(x, y) = queue.popleft()
			temp[0] += 1
			for i in range(8):
				tx = x + dx[i]
				ty = y + dy[i]
				if tx >= 0 and tx < rows and (ty >= 0) and (ty < cols) and (visited[tx][ty] == False) and (grid[tx][ty] == 1):
					visited[tx][ty] = True
					queue.append((tx, ty))

	def findMaxArea(self, grid):
		rows = len(grid)
		cols = len(grid[0])
		ans = 0
		visited = [[False for i in range(cols)] for i in range(rows)]
		for i in range(rows):
			for j in range(cols):
				if visited[i][j] == False and grid[i][j] == 1:
					temp = [0]
					self.BFS(i, j, rows, cols, visited, grid, temp)
					ans = max(temp[0], ans)
		return ans


import sys

class Solution:

	def isvalid(self, grid, i, j, visit):
		row = len(grid)
		col = len(grid[0])
		if i < 0 or j < 0 or i >= row or (j >= col) or (visit[i][j] == 1) or (grid[i][j] == 0):
			return False
		return True

	def dfs(self, grid, visit, start):
		(i, j) = (start[0], start[1])
		visit[i][j] = 1
		sm = 0
		for (u, v) in [[1, 0], [0, 1], [-1, 0], [0, -1], [-1, 1], [1, 1], [-1, -1], [1, -1]]:
			if self.isvalid(grid, i + u, j + v, visit):
				sm += self.dfs(grid, visit, (i + u, j + v))
		return sm + 1

	def findMaxArea(self, grid):
		row = len(grid)
		col = len(grid[0])
		vis = [[0] * col for i in range(row)]
		ans = -sys.maxsize
		for i in range(row):
			for j in range(col):
				if grid[i][j] == 1 and vis[i][j] == 0:
					temp = self.dfs(grid, vis, (i, j))
					ans = max(ans, temp)
		return ans if ans != -sys.maxsize else 0


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):
	dx = [-1, 0, 1, -1, 1, -1, 0, 1]
	dy = [-1, -1, -1, 0, 0, 1, 1, 1]
	avail = []
	for w in range(len(dy)):
		x = i + dx[w]
		y = j + dy[w]
		if isInside(x, y, n, m) and grid[x][y] == 1:
			avail.append((x, y))
	return avail

class Solution:

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = [[False] * m for i in range(n)]
		q = deque()
		mx = 0
		for i in range(n):
			for j in range(m):
				if not visited[i][j]:
					if grid[i][j] == 1:
						q.append((i, j))
						visited[i][j] = True
						mxCounter = 0
						while q:
							mxCounter += 1
							current = q.popleft()
							neighs = getAvailableNeighbors(current[0], current[1], n, m, grid)
							for ne in neighs:
								if not visited[ne[0]][ne[1]]:
									visited[ne[0]][ne[1]] = True
									q.append((ne[0], ne[1]))
						if mxCounter > mx:
							mx = mxCounter
		return mx


class Solution:

	def findMaxArea(self, grid):
		global ans
		ans = 0
		global area
		area = 0
		x = [-1, -1, -1, 0, 1, 1, 1, 0]
		y = [-1, 0, 1, -1, -1, 0, 1, 1]

		def dfs(grid, i, j):
			grid[i][j] = 2
			global area
			area += 1
			for k in range(8):
				x1 = x[k] + i
				y1 = y[k] + j
				if (x1 >= 0 and x1 < len(grid)) and (y1 >= 0 and y1 < len(grid[0])):
					if grid[x1][y1] == 1:
						dfs(grid, x1, y1)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					area = 0
					dfs(grid, i, j)
					ans = max(ans, area)
		return ans


from collections import deque

class Solution:

	def findMaxArea(self, grid):

		def dfs(grid, a, b, visited, cnt):
			visited.add((a, b))
			for (x, y) in [(a, b + 1), (a + 1, b), (a + 1, b + 1), (a - 1, b - 1), (a - 1, b), (a - 1, b + 1), (a + 1, b - 1), (a, b - 1)]:
				if x >= 0 and x < len(grid) and (y >= 0) and (y < len(grid[0])) and (grid[x][y] == 1):
					if (x, y) not in visited:
						cnt[0] += 1
						dfs(grid, x, y, visited, cnt)
		visited = set()
		coor = []
		(c0, c, ans) = (-999, 0, 0)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1 and (i, j) not in visited:
					cnt = [1]
					dfs(grid, i, j, visited, cnt)
					ans = max(ans, cnt[0])
		return ans


class Solution:

	def findMaxArea(self, grid):
		offsets = [(0, 1), (1, 0), (-1, 0), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]

		def get_neighbors(row, col):
			neighbors = []
			for offset in offsets:
				next_row = row + offset[0]
				next_col = col + offset[1]
				if next_row < 0 or next_row >= len(grid):
					continue
				if next_col < 0 or next_col >= len(grid[0]):
					continue
				if grid[next_row][next_col] != 1:
					continue
				neighbors.append((next_row, next_col))
			return neighbors

		def connect_ones(row, col):
			current_size = len(visited)
			visited.add((row, col))
			neighbors = get_neighbors(row, col)
			area = 1
			for neighbor in neighbors:
				if neighbor in visited:
					continue
				area += connect_ones(neighbor[0], neighbor[1])
			return area
		visited = set()
		max_area = 0
		for row in range(len(grid)):
			for col in range(len(grid[0])):
				if (row, col) in visited:
					continue
				if grid[row][col] != 1:
					continue
				area = connect_ones(row, col)
				max_area = max(area, max_area)
		return max_area


class Solution:

	def findMaxArea(self, grid):
		cnt = 0
		max_area = 0
		dirs = [[-1, 0], [1, 0], [0, -1], [0, 1], [1, 1], [-1, -1], [-1, 1], [1, -1]]

		def dfs(i, j):
			nonlocal dirs, cnt
			if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and (grid[i][j] == 1):
				grid[i][j] = 0
				cnt += 1
				for dir in dirs:
					dfs(i + dir[0], j + dir[1])
				return cnt
			return 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					cnt = 0
					max_area = max(max_area, dfs(i, j))
		return max_area


class Solution:

	def findMaxArea(self, grid):
		cnt = 0
		max_cnt = 0
		directions = ((0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (-1, 1), (-1, -1), (1, -1))

		def dfs(r, c):
			nonlocal cnt
			if r < 0 or r >= len(grid) or c < 0 or (c >= len(grid[0])) or (grid[r][c] != 1):
				return
			cnt += 1
			grid[r][c] = 0
			for direction in directions:
				dfs(r + direction[0], c + direction[1])
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					cnt = 0
					dfs(i, j)
					max_cnt = max(max_cnt, cnt)
		return max_cnt


from collections import deque

class Solution:

	def bfs(self, row, col, vis, grid, curMax):
		vis[row][col] = 1
		q = deque()
		q.append([row, col])
		n = len(grid)
		m = len(grid[0])
		while q:
			ele = q.popleft()
			row = ele[0]
			col = ele[1]
			for delrow in range(-1, 2, 1):
				for delcol in range(-1, 2, 1):
					nrow = row + delrow
					ncol = col + delcol
					if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (grid[nrow][ncol] == 1) and (vis[nrow][ncol] != 1):
						vis[nrow][ncol] = 1
						curMax += 1
						q.append([nrow, ncol])
		return curMax

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		vis = [[0] * m for i in range(n)]
		countMax = 0
		for row in range(n):
			for col in range(m):
				if vis[row][col] != 1 and grid[row][col] == 1:
					curMax = self.bfs(row, col, vis, grid, 1)
					if curMax > countMax:
						countMax = curMax
		return countMax


class Solution:

	def findMaxArea(self, grid):
		rows = len(grid)
		cols = len(grid[0])
		visited = set()

		def dfs(r, c):
			if r not in range(rows) or c not in range(cols) or grid[r][c] == 0 or ((r, c) in visited):
				return 0
			visited.add((r, c))
			return 1 + dfs(r + 1, c) + dfs(r + 1, c + 1) + dfs(r - 1, c) + dfs(r - 1, c + 1) + dfs(r, c + 1) + dfs(r - 1, c - 1) + dfs(r, c - 1) + dfs(r + 1, c - 1)
		area = 0
		for r in range(rows):
			for c in range(cols):
				if grid[r][c] == 1 and (r, c) not in visited:
					area = max(area, dfs(r, c))
		return area


from collections import defaultdict

class Solution:

	def dfs(self, r, c):
		Solution.visited[r, c] = True
		count = 0
		for (dr, dc) in Solution.moves:
			(row, col) = (r + dr, c + dc)
			if 0 <= row < Solution.rows and 0 <= col < Solution.cols and Solution.grid[row][col] and (not Solution.visited[row, col]):
				count += self.dfs(row, col)
		return count + 1

	def findMaxArea(self, grid):
		if not grid:
			return 0
		ma = 0
		Solution.visited = defaultdict(bool)
		(Solution.rows, Solution.cols) = (len(grid), len(grid[0]))
		Solution.grid = grid
		Solution.moves = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
		for i in range(Solution.rows):
			for j in range(Solution.cols):
				if grid[i][j] and (not Solution.visited[i, j]):
					ma = max(ma, self.dfs(i, j))
		return ma


from collections import deque

class Solution:

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = [[0 for i in range(m)] for j in range(n)]
		maxi = 0
		for i in range(0, n):
			for j in range(0, m):
				if visited[i][j] == 0 and grid[i][j] == 1:
					maxi = max(maxi, self.bfs(i, j, visited, grid))
		return maxi

	def bfs(self, row, col, visited, grid):
		count = 0
		queue = deque()
		queue.append([row, col])
		visited[row][col] = 1
		delrow = [-1, -1, -1, 0, 0, 1, 1, 1]
		delcol = [-1, 0, 1, -1, 1, -1, 0, 1]
		while queue:
			ele = queue.popleft()
			r = ele[0]
			c = ele[1]
			count += 1
			for i in range(0, 8):
				nrow = r + delrow[i]
				ncol = c + delcol[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (visited[nrow][ncol] == 0) and (grid[nrow][ncol] == 1):
					queue.append([nrow, ncol])
					visited[nrow][ncol] = 1
		return count


class Solution:

	def findMaxArea(self, grid):
		directions = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

		def dfs(i, j):
			if i < 0 or j < 0 or i >= r or (j >= c) or (grid[i][j] <= 0):
				return 0
			area = 1
			grid[i][j] = -1
			for d in directions:
				(x, y) = (i + d[0], j + d[1])
				area += dfs(x, y)
			return area
		max_area = 0
		(r, c) = (len(grid), len(grid[0]))
		for i in range(r):
			for j in range(c):
				if grid[i][j] == 1:
					max_area = max(max_area, dfs(i, j))
		return max_area


class Solution:

	def findMaxArea(self, gp):
		count = 0
		visted = set()
		M = 0
		for i in range(len(gp)):
			for j in range(len(gp[0])):
				if (i, j) not in visted and gp[i][j] != 0:
					self.count = 0
					self.Dfs(gp, i, j, visted)
					if self.count > M:
						M = self.count
		return M
		return count

	def safe(self, x, y, gp):
		if x >= 0 and x < len(gp) and (y >= 0) and (y < len(gp[0])) and (gp[x][y] == 1):
			return True
		return False

	def Dfs(self, gp, i, j, visted):
		if gp[i][j] == 1:
			self.count += 1
		visted.add((i, j))
		List = [(1, 0), (0, 1), (0, -1), (-1, 0), (-1, -1), (1, 1), (-1, 1), (1, -1)]
		for (a, b) in List:
			if self.safe(i + a, j + b, gp) == True and (i + a, j + b) not in visted:
				self.Dfs(gp, i + a, j + b, visted)


from collections import deque

class Solution:

	def findMaxArea(self, grid):
		q = deque()
		visited = set()
		directions = [(0, 1), (1, 0), (-1, 0), (0, -1), (-1, 1), (1, 1), (1, -1), (-1, -1)]
		n = len(grid)
		m = len(grid[0])
		if n == 1 and m == 1:
			if grid[0][0] == 1:
				return 1
			else:
				return 0
		max_count = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and (i, j) not in visited:
					q.append((i, j))
					visited.add((i, j))
					count = 1
					max_count = max(max_count, count)
					while q:
						(r, c) = q.popleft()
						for (k, l) in directions:
							row = k + r
							col = l + c
							if row in range(n) and col in range(m) and (grid[row][col] == 1) and ((row, col) not in visited):
								count += 1
								visited.add((row, col))
								q.append((row, col))
								max_count = max(max_count, count)
		return max_count


class DS:

	def __init__(self, n):
		self.parents = [0] * n
		self.sizes = [0] * n
		for i in range(n):
			self.parents[i] = i
			self.sizes[i] = 1

	def find(self, u):
		if self.parents[u] == u:
			return u
		else:
			self.parents[u] = self.find(self.parents[u])
			return self.parents[u]

	def union(self, u, v):
		rootu = self.find(u)
		rootv = self.find(v)
		if rootu == rootv:
			return
		if self.sizes[rootu] < self.sizes[rootv]:
			self.parents[rootu] = rootv
			self.sizes[rootv] += self.sizes[rootu]
		else:
			self.parents[rootv] = rootu
			self.sizes[rootu] += self.sizes[rootv]

class Solution:

	def findMaxArea(self, grid):
		R = len(grid)
		C = len(grid[0])
		ds = DS(R * C)
		for row in range(R):
			for col in range(C):
				if grid[row][col] == 1:
					dxy = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]]
					for (dx, dy) in dxy:
						n_row = row + dx
						n_col = col + dy
						if n_row >= 0 and n_row < R and (n_col >= 0) and (n_col < C) and (grid[n_row][n_col] == 1):
							node_no = row * C + col
							adj_node_no = n_row * C + n_col
							ds.union(node_no, adj_node_no)
		max_area = 0
		for row in range(R):
			for col in range(C):
				if grid[row][col] == 1:
					node_no = row * C + col
					if ds.find(node_no) == node_no:
						area = ds.sizes[node_no]
						max_area = max(max_area, area)
		return max_area


class Solution:

	def __init__(self):
		self.count = 0

	def dfs(self, grid, i, j, rows, cols):
		if i < 0 or i >= rows or j < 0 or (j >= cols) or (grid[i][j] != 1):
			return
		grid[i][j] = 0
		self.count = self.count + 1
		self.dfs(grid, i + 1, j, rows, cols)
		self.dfs(grid, i - 1, j, rows, cols)
		self.dfs(grid, i, j + 1, rows, cols)
		self.dfs(grid, i, j - 1, rows, cols)
		self.dfs(grid, i - 1, j - 1, rows, cols)
		self.dfs(grid, i + 1, j - 1, rows, cols)
		self.dfs(grid, i + 1, j + 1, rows, cols)
		self.dfs(grid, i - 1, j + 1, rows, cols)

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		count = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					self.count = 0
					self.dfs(grid, i, j, n, m)
					count = max(count, self.count)
		return count


class Solution:

	def dfs(self, row, col, grid, visited, R, C):
		if row >= 0 and row < R and (col >= 0) and (col < C) and (grid[row][col] == 1) and (not visited[row][col]):
			visited[row][col] = True
			count = 1
			dxy = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]]
			for (dx, dy) in dxy:
				n_row = row + dx
				n_col = col + dy
				count += self.dfs(n_row, n_col, grid, visited, R, C)
			return count
		return 0

	def findMaxArea(self, grid):
		R = len(grid)
		C = len(grid[0])
		visited = [[False for _ in range(C)] for _ in range(R)]
		max_area = 0
		for row in range(R):
			for col in range(C):
				if grid[row][col] == 1 and (not visited[row][col]):
					area = self.dfs(row, col, grid, visited, R, C)
					max_area = max(max_area, area)
		return max_area


class Solution:

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])

		def dfs(i, j):
			for k in range(len(a)):
				if i + a[k][0] >= 0 and i + a[k][0] < n and (j + a[k][1] >= 0) and (j + a[k][1] < m):
					if h[i + a[k][0]][j + a[k][1]] == 1:
						continue
					h[i + a[k][0]][j + a[k][1]] = 1
					if grid[i + a[k][0]][j + a[k][1]] == 1:
						count[0] += 1
						dfs(i + a[k][0], j + a[k][1])
			return count
		a = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, 1], [-1, -1], [1, -1], [1, 1]]
		h = [[0 for j in range(m)] for i in range(n)]
		a1 = 0
		for i in range(n):
			for j in range(m):
				if h[i][j] == 1:
					continue
				if grid[i][j] == 1 and h[i][j] == 0:
					h[i][j] = 1
					count = [1]
					ans = dfs(i, j)
					a1 = max(a1, count[0])
		return a1


class Solution:

	def bfs(self, vis, grid, n, m, i, j):
		counti = 1
		vis[i][j] = 1
		q = [(i, j)]
		while q:
			(s, t) = q.pop(0)
			if s - 1 > -1 and grid[s - 1][t] == 1 and (vis[s - 1][t] == 0):
				q.append((s - 1, t))
				vis[s - 1][t] = 1
				counti += 1
			if t - 1 > -1 and grid[s][t - 1] == 1 and (vis[s][t - 1] == 0):
				q.append((s, t - 1))
				vis[s][t - 1] = 1
				counti += 1
			if s - 1 > -1 and t - 1 > -1 and (grid[s - 1][t - 1] == 1) and (vis[s - 1][t - 1] == 0):
				q.append((s - 1, t - 1))
				vis[s - 1][t - 1] = 1
				counti += 1
			if s - 1 > -1 and t + 1 < m and (grid[s - 1][t + 1] == 1) and (vis[s - 1][t + 1] == 0):
				q.append((s - 1, t + 1))
				vis[s - 1][t + 1] = 1
				counti += 1
			if s + 1 < n and grid[s + 1][t] == 1 and (vis[s + 1][t] == 0):
				q.append((s + 1, t))
				vis[s + 1][t] = 1
				counti += 1
			if t + 1 < m and grid[s][t + 1] == 1 and (vis[s][t + 1] == 0):
				q.append((s, t + 1))
				vis[s][t + 1] = 1
				counti += 1
			if s + 1 < n and t + 1 < m and (grid[s + 1][t + 1] == 1) and (vis[s + 1][t + 1] == 0):
				q.append((s + 1, t + 1))
				vis[s + 1][t + 1] = 1
				counti += 1
			if s + 1 < n and t - 1 > -1 and (grid[s + 1][t - 1] == 1) and (vis[s + 1][t - 1] == 0):
				q.append((s + 1, t - 1))
				vis[s + 1][t - 1] = 1
				counti += 1
		return counti

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		vis = [[0] * m for _ in range(n)]
		maxi = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and vis[i][j] == 0:
					maxi = max(maxi, self.bfs(vis, grid, n, m, i, j))
		return maxi


from collections import deque

def bfs(i, j, visit, grid, ans):
	an = ans
	visit[i][j] = 1
	q = deque()
	q.append([i, j])
	while q:
		new = q.popleft()
		row = new[0]
		col = new[1]
		for i in range(-1, 2):
			for j in range(-1, 2):
				nrow = row + i
				ncol = col + j
				if nrow >= 0 and nrow < len(grid) and (ncol >= 0) and (ncol < len(grid[0])) and (visit[nrow][ncol] == 0) and (grid[nrow][ncol] == 1):
					an += 1
					visit[nrow][ncol] = 1
					q.append([nrow, ncol])
	return an

class Solution:

	def findMaxArea(self, grid):
		visit = []
		n = len(grid)
		m = len(grid[0])
		for i in range(n):
			visit.append([0 for _ in range(m)])
		max_area = 0
		for i in range(n):
			for j in range(m):
				if visit[i][j] == 0 and grid[i][j] == 1:
					ans = bfs(i, j, visit, grid, 1)
					max_area = max(max_area, ans)
		return max_area


def traverse(grid, vis, i, j):
	if i < 0 or j < 0 or i == len(grid) or (j == len(grid[0])) or vis[i][j] or (grid[i][j] == 0):
		return 0
	vis[i][j] = 1
	ans = 1
	ans += traverse(grid, vis, i + 1, j)
	ans += traverse(grid, vis, i - 1, j)
	ans += traverse(grid, vis, i, j + 1)
	ans += traverse(grid, vis, i, j - 1)
	ans += traverse(grid, vis, i + 1, j - 1)
	ans += traverse(grid, vis, i + 1, j + 1)
	ans += traverse(grid, vis, i - 1, j + 1)
	ans += traverse(grid, vis, i - 1, j - 1)
	return ans

class Solution:

	def findMaxArea(self, grid):
		ans = 0
		vis = [[0 for i in range(len(grid[0]))] for i in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if vis[i][j] == 0 and grid[i][j]:
					ans = max(ans, traverse(grid, vis, i, j))
		return ans


class Solution:

	def findMaxArea(self, grid):
		m = len(grid)
		n = len(grid[0])
		dx = [-1, -1, -1, 0, 0, 1, 1, 1]
		dy = [-1, 0, 1, -1, 1, -1, 0, 1]

		def isSafe(mat, row, col, m, n, visit):
			return row >= 0 and row < m and (col >= 0) and (col < n) and mat[row][col] and (not visit[row][col])

		def dfs(mat, row, col, dx, dy, visit, count):
			visit[row][col] = 1
			for i in range(8):
				if isSafe(mat, row + dx[i], col + dy[i], m, n, visit):
					count[0] += 1
					dfs(mat, row + dx[i], col + dy[i], dx, dy, visit, count)
		result = 0
		visit = [[0] * n for i in range(m)]
		for i in range(m):
			for j in range(n):
				if grid[i][j] and (not visit[i][j]):
					count = [1]
					dfs(grid, i, j, dx, dy, visit, count)
					result = max(result, count[0])
		return result


class Solution:

	def area(self, v, grid, i, j):
		x = 1
		if 0 <= i - 1 < len(grid) and 0 <= j - 1 < len(grid[0]):
			if grid[i - 1][j - 1] == 1:
				if v[i - 1][j - 1]:
					v[i - 1][j - 1] = False
					x += Solution.area(self, v, grid, i - 1, j - 1)
		if 0 <= i - 1 < len(grid) and 0 <= j < len(grid[0]):
			if grid[i - 1][j] == 1:
				if v[i - 1][j]:
					v[i - 1][j] = False
					x += Solution.area(self, v, grid, i - 1, j)
		if 0 <= i - 1 < len(grid) and 0 <= j + 1 < len(grid[0]):
			if grid[i - 1][j + 1] == 1:
				if v[i - 1][j + 1]:
					v[i - 1][j + 1] = False
					x += Solution.area(self, v, grid, i - 1, j + 1)
		if 0 <= i < len(grid) and 0 <= j - 1 < len(grid[0]):
			if grid[i][j - 1] == 1:
				if v[i][j - 1]:
					v[i][j - 1] = False
					x += Solution.area(self, v, grid, i, j - 1)
		if 0 <= i < len(grid) and 0 <= j + 1 < len(grid[0]):
			if grid[i][j + 1] == 1:
				if v[i][j + 1]:
					v[i][j + 1] = False
					x += Solution.area(self, v, grid, i, j + 1)
		if 0 <= i + 1 < len(grid) and 0 <= j - 1 < len(grid[0]):
			if grid[i + 1][j - 1] == 1:
				if v[i + 1][j - 1]:
					v[i + 1][j - 1] = False
					x += Solution.area(self, v, grid, i + 1, j - 1)
		if 0 <= i + 1 < len(grid) and 0 <= j < len(grid[0]):
			if grid[i + 1][j] == 1:
				if v[i + 1][j]:
					v[i + 1][j] = False
					x += Solution.area(self, v, grid, i + 1, j)
		if 0 <= i + 1 < len(grid) and 0 <= j + 1 < len(grid[0]):
			if grid[i + 1][j + 1] == 1:
				if v[i + 1][j + 1]:
					v[i + 1][j + 1] = False
					x += Solution.area(self, v, grid, i + 1, j + 1)
		return x

	def findMaxArea(self, grid):
		ans = 0
		visit = [[True for i in range(len(grid[0]))] for j in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if visit[i][j]:
					if grid[i][j] == 1:
						visit[i][j] = False
						x = Solution.area(self, visit, grid, i, j)
						ans = max(x, ans)
		return ans


class Solution:

	def dfs(self, x, y, visited, grid):
		visited[x][y] = True
		ans = 0
		neighbours = [(x - 1, y - 1), (x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y), (x + 1, y + 1)]
		for i in neighbours:
			if 0 <= i[0] < len(grid) and 0 <= i[1] < len(grid[0]) and (visited[i[0]][i[1]] == False) and (grid[i[0]][i[1]] == 1):
				blu = self.dfs(i[0], i[1], visited, grid)
				ans += blu
		return 1 + ans

	def findMaxArea(self, grid):
		ma = 0
		visited = [[False for i in range(len(grid[0]))] for j in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if visited[i][j] == False and grid[i][j] == 1:
					x = self.dfs(i, j, visited, grid)
					if x > ma:
						ma = x
		return ma


class Solution:

	def findMaxArea(self, grid):
		m = len(grid)
		n = len(grid[0])
		ans = []
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					smallAns = self.dfs(grid, i, j, m, n)
					ans.append(smallAns)
		if len(ans) == 0:
			return 0
		return max(ans)

	def dfs(self, grid, i, j, m, n):
		if i < 0 or i >= m or j < 0 or (j >= n) or (grid[i][j] != 1):
			return 0
		grid[i][j] = -1
		ans1 = self.dfs(grid, i - 1, j, m, n)
		ans2 = self.dfs(grid, i + 1, j, m, n)
		ans3 = self.dfs(grid, i, j + 1, m, n)
		ans4 = self.dfs(grid, i, j - 1, m, n)
		ans5 = self.dfs(grid, i + 1, j + 1, m, n)
		ans6 = self.dfs(grid, i + 1, j - 1, m, n)
		ans7 = self.dfs(grid, i - 1, j + 1, m, n)
		ans8 = self.dfs(grid, i - 1, j - 1, m, n)
		ans = 1 + ans1 + ans2 + ans3 + ans4 + ans5 + ans6 + ans7 + ans8
		return ans


class Solution:

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		vis = [[0 for j in range(m)] for i in range(n)]
		maxi = 0
		for i in range(n):
			for j in range(m):
				if not vis[i][j] and grid[i][j] == 1:
					cnt = 0
					vis[i][j] = 1
					q = [[i, j]]
					while q:
						t = q.pop(0)
						x = t[0]
						y = t[1]
						cnt += 1
						for a in range(-1, 2):
							for b in range(-1, 2):
								if 0 <= x + a < n and 0 <= y + b < m and (grid[x + a][y + b] == 1) and (vis[x + a][y + b] == 0):
									vis[x + a][y + b] = 1
									q.append([x + a, y + b])
					maxi = max(maxi, cnt)
		return maxi


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def __init__(self):
		self.tempx = [0, -1, 0, 1, -1, -1, 1, 1]
		self.tempy = [-1, 0, 1, 0, -1, 1, 1, -1]

	def findMaxArea(self, grid):
		rows = len(grid)
		cols = len(grid[0])
		q = []
		maxi = 0
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] == 1:
					count = [0]
					grid[i][j] = 2
					self.bfs(i, j, grid, rows, cols, count)
					maxi = max(maxi, count[0])
		return maxi

	def dfs(self, i, j, grid, rows, cols, count):
		grid[i][j] = 2
		count[0] += 1
		for k in range(8):
			new_x = i + self.tempx[k]
			new_y = j + self.tempy[k]
			if self.isValid(grid, new_x, new_y, rows, cols):
				self.dfs(new_x, new_y, grid, rows, cols, count)

	def bfs(self, i, j, grid, rows, cols, count):
		q = [(i, j)]
		count[0] += 1
		while q:
			temp = q.pop(0)
			x = temp[0]
			y = temp[1]
			for k in range(8):
				new_x = x + self.tempx[k]
				new_y = y + self.tempy[k]
				if self.isValid(grid, new_x, new_y, rows, cols):
					grid[new_x][new_y] = 2
					q.append((new_x, new_y))
					count[0] += 1

	def isValid(self, grid, x, y, rows, cols):
		if x >= 0 and x < rows and (y >= 0) and (y < cols) and (grid[x][y] == 1):
			return True
		else:
			return False


class Solution:

	def bfs(self, r, c, grid, visited):
		q = []
		visited[r][c] = 1
		q.append((r, c))
		n = len(grid)
		m = len(grid[r])
		area = 1
		while len(q) > 0:
			(r, c) = q.pop(0)
			for dr in range(-1, 2):
				for dc in range(-1, 2):
					row = r + dr
					col = c + dc
					if n > row and row >= 0 and (m > col) and (col >= 0) and (grid[row][col] == 1) and (visited[row][col] == 0):
						q.append((row, col))
						visited[row][col] = 1
						area += 1
		return area

	def findMaxArea(self, grid):
		if grid is None:
			return 0
		islands_area = [0]
		visited = [[0 for i in range(len(grid[j]))] for j in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[i])):
				if visited[i][j] == 0 and grid[i][j] == 1:
					area = self.bfs(i, j, grid, visited)
					islands_area.append(area)
		return max(islands_area)


class Solution:

	def findMaxArea(self, grid):
		n = len(grid)
		m = len(grid[0])
		ans = 0
		self.count = 0
		dirs = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1]]

		def check(i, j):
			if i >= 0 and j >= 0 and (i < n) and (j < m) and (grid[i][j] == 1):
				return True
			else:
				return False

		def dfs(i, j):
			grid[i][j] = 0
			for d in dirs:
				x = i + d[0]
				y = j + d[1]
				if check(x, y) == True:
					self.count += 1
					dfs(x, y)
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					self.count = 1
					dfs(i, j)
					ans = max(ans, self.count)
		return ans