Consider a matrix where each cell contains either a $0$ or a $1$.  Any cell containing a $1$ is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally.  In the following grid, all cells marked X are connected to the cell marked Y.

XXX
XYX  
XXX    

If one or more filled cells are also connected, they form a region. Note that each cell in a region is connected to zero or more cells in the region but is not necessarily directly connected to all the other cells in the region.

Given an $n\times m$ matrix, find and print the number of cells in the largest region in the matrix. Note that there may be more than one region in the matrix.

For example, there are two regions in the following $3\times3$ matrix.  The larger region at the top left contains $3$ cells.  The smaller one at the bottom right contains $1$.  

110
100
001

Function Description  

Complete the connectedCell function in the editor below.  

connectedCell has the following parameter(s): 

- int matrix[n][m]: $matrix[i]$ represents the $i^{\mbox{th}}$ row of the matrix  

Returns 

- int: the area of the largest region  

Input Format

The first line contains an integer $n$, the number of rows in the matrix. 

The second line contains an integer $m$, the number of columns in the matrix. 

Each of the next $n$ lines contains $m$ space-separated integers $matrix[i][j]$.

Constraints

$0<n,m<10$

Sample Input
STDIN       Function
-----       --------
4           n = 4
4           m = 4
1 1 0 0     grid = [[1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 1, 0], [1, 0, 0, 0]]
0 1 1 0
0 0 1 0
1 0 0 0

Sample Output
5

Explanation

The diagram below depicts two regions of the matrix.  Connected regions are filled with X or Y.  Zeros are replaced with dots for clarity.  

X X . .
. X X .
. . X .
Y . . .

The larger region has $5$ cells, marked X.

Source: hackerrank | Difficulty: MEDIUM
Tags: Complete search


Solutions:
rows = int(input())
cols = int(input())
mat = []
for _ in range(rows):
	mat.append([int(x == '1') for x in input().strip().split(' ')])
ones = set()
for row in range(rows):
	for col in range(cols):
		if mat[row][col]:
			ones.add((row, col))
regions = []
while ones:
	n = ones.pop()
	region = [n]
	regions.append(region)
	unchecked = [n]
	while unchecked:
		(xr, xc) = unchecked.pop()
		for r in [-1, 0, 1]:
			for c in [-1, 0, 1]:
				p = (xr + r, xc + c)
				if p in ones:
					ones.remove(p)
					region.append(p)
					unchecked.append(p)
print(max((len(region) for region in regions), default=0))


def spread(x, y, m):
	try:
		if x < 0 or y < 0 or x >= len(m[0]) or (y >= len(m)) or (m[y][x] == '0'):
			return 0
		else:
			m[y][x] = '0'
			return spread(x - 1, y, m) + spread(x + 1, y, m) + spread(x, y - 1, m) + spread(x, y + 1, m) + spread(x - 1, y + 1, m) + spread(x + 1, y - 1, m) + spread(x - 1, y - 1, m) + spread(x + 1, y + 1, m) + 1
	except:
		return 0
n = int(input())
h = int(input())
m = []
for i in range(n):
	m.append(input().split())
s = 0
for i in range(h):
	for j in range(n):
		s = max(s, spread(i, j, m))
print(s)


nr = int(input())
nc = int(input())
mat1 = []
for i in range(nr):
	mat1.append([int(s) for s in str(input()).strip().split()])

def isNeighbor(row, col, c):
	if c is None:
		return False
	for item in c:
		if abs(item[0] - row) <= 1 and abs(item[1] - col) <= 1:
			return True
	return False

def getNeighborComp(row, col, comps):
	result = []
	if len(comps) == 0:
		return []
	else:
		for c in comps:
			if isNeighbor(row, col, c):
				result.append(c)
		return result

def ans(mat):
	components = []
	for row in range(len(mat)):
		for col in range(len(mat[0])):
			if mat[row][col] == 1:
				neighbors = getNeighborComp(row, col, components[:])
				if len(neighbors) == 0:
					x = []
					x.append((row, col))
					components.append(x)
				elif len(neighbors) == 1:
					temp = neighbors[0][:]
					components.remove(temp)
					temp.append((row, col))
					components.append(temp)
				elif len(neighbors) == 2:
					components.remove(neighbors[0])
					components.remove(neighbors[1])
					temp = neighbors[0][:]
					temp.extend(neighbors[1])
					temp.append((row, col))
					components.append(temp)
	return components
print(max([len(c) for c in ans(mat1)]))


from math import sqrt, ceil
import sys

class Node:

	def __init__(self, data, coords):
		self.data = data
		self.coords = coords

	def distance(self, otherNode):
		return sqrt((self.coords[0] - otherNode.coords[0]) ** 2 + (self.coords[1] - otherNode.coords[1]) ** 2)

	def get_connected_nodes(self, mat):
		row = self.coords[0]
		col = self.coords[1]
		min_row = max(row - 1, 0)
		max_row = min(row + 1, len(mat) - 1)
		min_col = max(col - 1, 0)
		max_col = min(col + 1, len(mat[0]) - 1)
		nodes = set()
		for i in range(min_row, max_row + 1):
			for j in range(min_col, max_col + 1):
				if mat[i][j].data == 1 and self.distance(mat[i][j]) <= sqrt(2):
					nodes.add(mat[i][j])
		return nodes

	def __str__(self):
		return 'Node[{0}, {1}]'.format(str(self.data), str(self.coords))

def largest_region(mat):
	regions = []
	for row in mat:
		for node in row:
			if node.data == 1:
				nodes = node.get_connected_nodes(mat)
				region_found = False
				for region in regions:
					if len(nodes & region) != 0:
						region.update(nodes)
						region_found = True
				if not region_found:
					regions.append(nodes)
	max_region = 0
	for region in regions:
		max_region = max(len(region), max_region)
	return max_region
rows = int(input())
cols = int(input())
mat = []
for row in range(rows):
	mat.append([int(col) for col in input().strip().split(' ')])
for row in range(rows):
	for col in range(cols):
		mat[row][col] = Node(mat[row][col], (row, col))
print(largest_region(mat))


import collections

def getLargestRegion(mat, m, n):
	regions = [i for i in range(2, 102)]
	regIdx = 2
	regionSizes = {}
	for i in range(0, m):
		for j in range(0, n):
			if mat[i][j] == 1:
				mat[i][j] = regions[regIdx]
				regionSizes[regIdx] = 1
				(mat, regionSize) = checkAdj(mat, i, j, m, n, regions[regIdx], regionSizes[regIdx])
				regionSizes[regIdx] = regionSize
			regIdx += 1
	return max(regionSizes.values())

def checkAdj(mat, i, j, m, n, regionNum, regionSize):
	for cell in getAdjSet(i, j):
		if cell[0] >= 0 and cell[0] < m and (cell[1] >= 0) and (cell[1] < n):
			q = cell[0]
			r = cell[1]
			if mat[q][r] == 1:
				mat[q][r] = regionNum
				regionSize += 1
				newAdjSet = getAdjSet(cell[0], cell[1]) - getAdjSet(i, j)
				(mat, regionSize) = checkAdj(mat, cell[0], cell[1], m, n, newAdjSet, regionSize)
	return (mat, regionSize)

def getAdjSet(i, j):
	return {(i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1)}
m = int(input())
n = int(input())
str_mat = []
mat = []
for i in range(0, m):
	line = input().strip().split(' ')
	str_mat.append(line)
for row in str_mat:
	mat.append([int(i) for i in row])
print(getLargestRegion(mat, m, n))


max_size = 0
row = int(input())
col = int(input())
grid = []
edges = {}
neighbors = [lambda x: (x[0] + 1, x[1] + 1), lambda x: (x[0] - 1, x[1] + 1), lambda x: (x[0] + 1, x[1] - 1), lambda x: (x[0] - 1, x[1] - 1), lambda x: (x[0], x[1] + 1), lambda x: (x[0] + 1, x[1]), lambda x: (x[0] - 1, x[1]), lambda x: (x[0], x[1] - 1)]
for i in range(0, row):
	grid.append(input().split())
for ro in grid:
	r = ro.pop()
	for e in r:
		ro.append(int(e))
for r in range(0, row):
	for c in range(0, col):
		if int(grid[r][c]) == 1:
			new_edges = []
			for l in neighbors:
				new_edge = l((r, c))
				if new_edge[0] >= 0 and new_edge[0] < row and (new_edge[1] >= 0) and (new_edge[1] < col):
					if int(grid[new_edge[0]][new_edge[1]]) == 1:
						new_edges.append(new_edge)
			edges[r, c] = new_edges
for e in edges:
	size = 0
	visited = {}
	stack = []
	stack.append(e)
	while len(stack) > 0:
		current = stack.pop()
		if visited.get(current) == None:
			visited[current] = 1
			size += 1
			for neighbor in edges[current]:
				stack.append(neighbor)
	if size > max_size:
		max_size = size
print(max_size)


from collections import deque
R = int(input())
C = int(input())
M = [input().split() for _ in range(R)]

def region_size(i, j):
	size = 0
	q = deque()
	q.append((i, j))
	while len(q) > 0:
		(x, y) = q.popleft()
		if M[x][y] == '1':
			size += 1
			M[x][y] = 0
			if x > 0 and y > 0:
				q.append((x - 1, y - 1))
			if x > 0:
				q.append((x - 1, y))
			if y > 0:
				q.append((x, y - 1))
			if x < R - 1 and y < C - 1:
				q.append((x + 1, y + 1))
			if x < R - 1:
				q.append((x + 1, y))
			if y < C - 1:
				q.append((x, y + 1))
			if x > 0 and y < C - 1:
				q.append((x - 1, y + 1))
			if x < R - 1 and y > 0:
				q.append((x + 1, y - 1))
	return size

def scan():
	for i in range(R):
		for j in range(C):
			if M[i][j] == '1':
				return (i, j)
	return (-1, -1)
regions = []
while 1:
	(i, j) = scan()
	if i == -1 and j == -1:
		break
	else:
		regions.append(region_size(i, j))
regions.sort()
print(regions[-1])


m = int(input())
n = int(input())
cells = set([])
a = []
for _ in range(m):
	ins = input().split()
	a.append([int(x) for x in ins])
largest = 0
for row in range(m):
	for col in range(n):
		try:
			if a[row][col] == 1:
				cells.add((row, col))
				curr = 0
				while len(cells) != 0:
					curr += 1
					(_row, _col) = cells.pop()
					a[_row][_col] = 0
					up = _row > 0
					down = _row < m - 1
					left = _col > 0
					right = _col < n - 1
					if up:
						if a[_row - 1][_col] == 1:
							cells.add((_row - 1, _col))
						if left:
							if a[_row - 1][_col - 1] == 1:
								cells.add((_row - 1, _col - 1))
						if right:
							if a[_row - 1][_col + 1] == 1:
								cells.add((_row - 1, _col + 1))
					if down:
						if a[_row + 1][_col] == 1:
							cells.add((_row + 1, _col))
						if left:
							if a[_row + 1][_col - 1] == 1:
								cells.add((_row + 1, _col - 1))
						if right:
							if a[_row + 1][_col + 1] == 1:
								cells.add((_row + 1, _col + 1))
					if left:
						if a[_row][_col - 1] == 1:
							cells.add((_row, _col - 1))
					if right:
						if a[_row][_col + 1] == 1:
							cells.add((_row, _col + 1))
				largest = max(largest, curr)
		except:
			while True:
				pass
print(largest)


m = int(input())
n = int(input())
arr = []
for i in range(m):
	row = list(map(int, input().strip().split(' ')))
	arr.append(row)
traversal_mat = []
for i in range(m):
	traversal_mat.append([False] * n)
max_count = 0
for i in range(m):
	for j in range(n):
		if arr[i][j] == 0 or traversal_mat[i][j] == True:
			continue
		traversal_mat[i][j] = True
		traversal_list = set()
		traversal_list.add((i, j))
		count = 0
		while len(traversal_list) > 0:
			(ii, jj) = traversal_list.pop()
			count = count + 1
			if ii > 0 and arr[ii - 1][jj] == 1 and (traversal_mat[ii - 1][jj] == False):
				traversal_list.add((ii - 1, jj))
			if ii < m - 1 and arr[ii + 1][jj] == 1 and (traversal_mat[ii + 1][jj] == False):
				traversal_list.add((ii + 1, jj))
			if jj > 0 and arr[ii][jj - 1] == 1 and (traversal_mat[ii][jj - 1] == False):
				traversal_list.add((ii, jj - 1))
			if jj > 0 and ii > 0 and (arr[ii - 1][jj - 1] == 1) and (traversal_mat[ii - 1][jj - 1] == False):
				traversal_list.add((ii - 1, jj - 1))
			if jj > 0 and ii < m - 1 and (arr[ii + 1][jj - 1] == 1) and (traversal_mat[ii + 1][jj - 1] == False):
				traversal_list.add((ii + 1, jj - 1))
			if jj < n - 1 and arr[ii][jj + 1] == 1 and (traversal_mat[ii][jj + 1] == False):
				traversal_list.add((ii, jj + 1))
			if jj < n - 1 and ii > 0 and (arr[ii - 1][jj + 1] == 1) and (traversal_mat[ii - 1][jj + 1] == False):
				traversal_list.add((ii - 1, jj + 1))
			if jj < n - 1 and ii < m - 1 and (arr[ii + 1][jj + 1] == 1) and (traversal_mat[ii + 1][jj + 1] == False):
				traversal_list.add((ii + 1, jj + 1))
			traversal_mat[ii][jj] = True
		if max_count < count:
			max_count = count
print(max_count)


reached = []
(m, n) = (int(input()), int(input()))
mat = [[int(x) for x in input().split()] for y in range(m)]
a = [(-1, -1), (-1, 0), (-1, 0), (0, -1), (0, 0), (0, 1), (1, -1), (1, 0), (1, 1)]

def trav(i, j):
	if not 0 <= i < m or not 0 <= j < n or mat[i][j] == 0 or ((i, j) in reached):
		return 0
	s = 1
	reached.append((i, j))
	for (x, y) in a:
		s += trav(i + x, j + y)
	return s
maxsofar = 0
for i in range(m):
	for j in range(n):
		maxsofar = max(maxsofar, trav(i, j))
print(maxsofar)


def SearchMatrix(graph, i, j):
	matrices = []
	frontier = [(i, j)]
	while len(frontier) > 0:
		(i, j) = frontier.pop()
		if i + 1 < len(graph):
			if graph[i + 1][j] and frontier.count((i + 1, j)) == 0 and (matrices.count((i + 1, j)) == 0):
				frontier.append((i + 1, j))
			if j + 1 < len(graph[i]) and graph[i + 1][j + 1] and (frontier.count((i + 1, j + 1)) == 0) and (matrices.count((i + 1, j + 1)) == 0):
				frontier.append((i + 1, j + 1))
			if j - 1 >= 0 and graph[i + 1][j - 1] and (frontier.count((i + 1, j - 1)) == 0) and (matrices.count((i + 1, j - 1)) == 0):
				frontier.append((i + 1, j - 1))
		if i - 1 >= 0:
			if graph[i - 1][j] and frontier.count((i - 1, j)) == 0 and (matrices.count((i - 1, j)) == 0):
				frontier.append((i - 1, j))
			if j + 1 < len(graph) and frontier.count((i - 1, j + 1)) == 0 and (matrices.count((i - 1, j + 1)) == 0) and graph[i - 1][j + 1]:
				frontier.append((i - 1, j + 1))
			if j - 1 >= 0 and frontier.count((i - 1, j - 1)) == 0 and (matrices.count((i - 1, j - 1)) == 0) and graph[i - 1][j - 1]:
				frontier.append((i - 1, j - 1))
		if j + 1 < len(graph[i]) and graph[i][j + 1] and (matrices.count((i, j + 1)) == 0) and (frontier.count((i, j + 1)) == 0):
			frontier.append((i, j + 1))
		if j - 1 >= 0 and graph[i][j - 1] and (matrices.count((i, j - 1)) == 0) and (frontier.count((i, j - 1)) == 0):
			frontier.append((i, j - 1))
		matrices.append((i, j))
	return matrices

def inRegion(i, j, regions):
	for region in regions:
		if region.count((i, j)):
			return True
	return False
regions = []
m = int(input())
n = int(input())
graph = []
maxMat = 0
for _ in range(0, m):
	graph.append([int(x) for x in input().rstrip().split(' ')])
for i in range(0, m):
	for j in range(0, n):
		if not inRegion(i, j, regions) and graph[i][j]:
			curMat = SearchMatrix(graph, i, j)
			if len(curMat) > maxMat:
				maxMat = len(curMat)
			regions.append(curMat)
print(maxMat)


m = int(input())
n = int(input())
px = [1, 1, 0, -1, -1, -1, 0, 1]
py = [0, -1, -1, -1, 0, 1, 1, 1]
arr = []
for _ in range(m):
	lol = list(map(int, input().split()))
	arr.append(lol)
vis = [[0 for _ in range(n)] for _ in range(m)]

def bfs(x, y):
	q = [(x, y)]
	vis[x][y] = 1
	count = 0
	while len(q) > 0:
		p = q[0]
		q = q[1:]
		count += 1
		for i in range(8):
			nextx = p[0] + px[i]
			nexty = p[1] + py[i]
			if nextx >= 0 and nexty >= 0 and (nextx < m) and (nexty < n):
				if arr[nextx][nexty] == 1 and vis[nextx][nexty] == 0:
					q.append((nextx, nexty))
					vis[nextx][nexty] = 1
	return count
ans = 0
for i in range(m):
	for j in range(n):
		if vis[i][j] == 0 and arr[i][j] == 1:
			ans = max(ans, bfs(i, j))
print(ans)


from sys import stdin
M = int(stdin.readline())
N = int(stdin.readline())
X = []
for m in range(M):
	X.append([])
	l = stdin.readline().split()
	for n in range(N):
		i = 0 if int(l[n]) == 0 else m * N + n + 1
		X[-1].append(i)

def influence(m, n, x):
	if n < 0 or m < 0 or n >= N or (m >= M):
		return False
	if x != 0 and X[m][n] != 0:
		if x == X[m][n]:
			return False
		X[m][n] = min(x, X[m][n])
		return True
	return False
r = True
while r:
	r = False
	for m in range(M):
		for n in range(N):
			x = X[m][n]
			if x == 0:
				continue
			for dn in [-1, 0, 1]:
				for dm in [-1, 0, 1]:
					if dn != 0 or dm != 0:
						if influence(m + dm, n + dn, x):
							r = True
XL = [x for t in X for x in t]
m = 0
for v in set(XL):
	if v != 0:
		n = sum([x == v for x in XL])
		m = max(n, m)
print(m)


def blankRegion(i, j, mat):
	if mat[i][j] == 0:
		return 0
	mat[i][j] = 0
	return 1 + sum((blankRegion(x, y, mat) for (x, y) in adj(i, j)))

def wrapped(mat):
	r = len(mat)
	c = len(mat[0])
	out = [[0] * (c + 2)] + [[0] + mat[i] + [0] for i in range(r)] + [[0] * (c + 2)]
	return out
assert wrapped([[1, 0], [1, 1], [0, 1]]) == [[0, 0, 0, 0], [0, 1, 0, 0], [0, 1, 1, 0], [0, 0, 1, 0], [0, 0, 0, 0]]

def maxRegion(mat):
	(r, c) = (len(mat), len(mat[0]))
	mat = wrapped(mat)
	return max((blankRegion(i, j, mat) for i in range(1, r + 1) for j in range(1, c + 1)))

def adj(i, j):
	for x in (i - 1, i, i + 1):
		for y in (j - 1, j, j + 1):
			yield (x, y)
r = int(input())
c = int(input())
mat = [[int(entry) for entry in input().split()] for row in range(r)]
for row in mat:
	assert len(row) == c
print(maxRegion(mat))


def main():
	m = int(input())
	n = int(input())
	U = []
	for i in range(m):
		U.append([int(x) for x in input().split()])
	if m == 0 or n == 0:
		print(0)
		return
	connectedCell(m, n, U)

def connectedCell(m, n, U):
	maxx = 0
	mar = 2
	for i in range(m):
		for j in range(n):
			if U[i][j] == 1:
				count = mark(U, i, j, mar, m, n)
				if count >= maxx:
					maxx = count
				mar += 1
	print(maxx)

def mark(U, i, j, mar, m, n):
	count = 1
	U[i][j] = mar
	toMark = [(i, j)]
	while toMark:
		(ci, cj) = toMark.pop(0)
		for ri in range(max(ci - 1, 0), min(ci + 2, m)):
			for rj in range(max(cj - 1, 0), min(cj + 2, n)):
				if U[ri][rj] == 1:
					U[ri][rj] = mar
					count += 1
					toMark.append((ri, rj))
	return count
main()


import sys

def max_cell(g, rows, cols):

	def blob(r, c):
		result = 0
		if r < rows and r >= 0 and (c < cols) and (c >= 0):
			if g[r][c] > 0 and v[r][c] == 0:
				v[r][c] = 1
				result += g[r][c]
				result += blob(r + 1, c)
				result += blob(r - 1, c)
				result += blob(r, c + 1)
				result += blob(r, c - 1)
				result += blob(r + 1, c + 1)
				result += blob(r + 1, c - 1)
				result += blob(r - 1, c + 1)
				result += blob(r - 1, c - 1)
		return result
	res = 0
	v = [[0 for _ in range(cols)] for _ in range(rows)]
	for i in range(rows):
		for j in range(cols):
			res = max(res, blob(i, j))
	return res
grid = []
for (i, line) in enumerate(sys.stdin):
	if i == 0:
		r = int(line)
	elif i == 1:
		c = int(line)
	else:
		grid.append([int(x) for x in line.split()])
print(max_cell(grid, r, c))


M = int(input())
N = int(input())
grid = ['0' * (N + 2)]

def count_components(x, y):
	count = 0
	queue = [(x, y)]
	marked.add(x * N + y)
	while queue:
		count += 1
		(i, j) = queue.pop()
		for a in range(i - 1, i + 2):
			for b in range(j - 1, j + 2):
				if grid[a][b] == '1' and a * N + b not in marked:
					queue.append((a, b))
					marked.add(a * N + b)
	return count
for _ in range(M):
	grid.append('0' + input().replace(' ', '') + '0')
grid.append('0' * (N + 2))
marked = set()
maxn = 0
for i in range(1, M + 1):
	for j in range(1, N + 1):
		if grid[i][j] == '1' and i * N + M not in marked:
			maxn = max(maxn, count_components(i, j))
print(maxn)


row = int(input())
col = int(input())

def get_adj_reg(cells, x, y, col):
	regions = []
	if x - 1 >= 0:
		if cells[x - 1][y].startswith('R'):
			regions.append(cells[x - 1][y])
		if y + 1 < col and cells[x - 1][y + 1].startswith('R'):
			regions.append(cells[x - 1][y + 1])
	if y - 1 >= 0:
		if cells[x][y - 1].startswith('R'):
			regions.append(cells[x][y - 1])
		if x - 1 >= 0 and cells[x - 1][y - 1].startswith('R'):
			regions.append(cells[x - 1][y - 1])
	return regions

def get_latest_reg(sub_reg_dict, reg):
	while reg in sub_reg_dict:
		reg = sub_reg_dict[reg]
	return reg

def get_latest_regs(sub_reg_dict, regs):
	latest_regs = []
	for r in regs:
		latest_regs.append(get_latest_reg(sub_reg_dict, r))
	return latest_regs
max_area = 0
tmp_area = 0
sub_reg_dict = {}
reg_size_dict = {}
cells = [[a for a in input().split()] for i in range(row)]
for i in range(row):
	for j in range(col):
		if cells[i][j] == '1':
			adj_regs = list(set(get_latest_regs(sub_reg_dict, get_adj_reg(cells, i, j, col))))
			n_adj_regs = len(adj_regs)
			if n_adj_regs == 0:
				reg_name = 'R' + str(len(reg_size_dict) + 1)
				reg_size_dict[reg_name] = 1
				cells[i][j] = reg_name
				tmp_area = 1
			elif n_adj_regs == 1:
				adj_regs[0] = get_latest_reg(sub_reg_dict, adj_regs[0])
				cells[i][j] = adj_regs[0]
				reg_size_dict[adj_regs[0]] += 1
				tmp_area = reg_size_dict[adj_regs[0]]
			elif adj_regs[0] == adj_regs[1]:
				cells[i][j] = adj_regs[0]
				reg_size_dict[adj_regs[0]] += 1
				tmp_area = reg_size_dict[adj_regs[0]]
			else:
				reg_name = 'R' + str(len(reg_size_dict) + 1)
				cells[i][j] = reg_name
				reg_size_dict[reg_name] = reg_size_dict[adj_regs[0]] + reg_size_dict[adj_regs[1]] + 1
				sub_reg_dict[adj_regs[0]] = reg_name
				sub_reg_dict[adj_regs[1]] = reg_name
				tmp_area = reg_size_dict[reg_name]
			if tmp_area > max_area:
				max_area = tmp_area
print(max_area)


m = int(input())
n = int(input())
grid = [[int(i) for i in input().split()] for _ in range(m)]
n_cells = m * n
parents = [i for i in range(n_cells)]
ranks = [0] * n_cells

def find(i):
	if parents[i] != i:
		parents[i] = find(parents[i])
	return parents[i]

def union(i, j):
	i_root = find(i)
	j_root = find(j)
	if i_root == j_root:
		return
	if ranks[i_root] < ranks[j_root]:
		parents[i_root] = j_root
	elif ranks[i_root] > ranks[j_root]:
		parents[j_root] = i_root
	else:
		parents[j_root] = i_root
		ranks[i_root] += 1

def to_index(r, c):
	return r * n + c
for r in range(m):
	for c in range(n):
		if grid[r][c] != 1:
			continue
		if c > 0 and grid[r][c - 1] == 1:
			union(to_index(r, c), to_index(r, c - 1))
		if r > 0 and c > 0 and (grid[r - 1][c - 1] == 1):
			union(to_index(r, c), to_index(r - 1, c - 1))
		if r > 0 and grid[r - 1][c] == 1:
			union(to_index(r, c), to_index(r - 1, c))
		if r > 0 and c < n - 1 and (grid[r - 1][c + 1] == 1):
			union(to_index(r, c), to_index(r - 1, c + 1))
counts = [0] * n_cells
for i in range(n_cells):
	counts[find(i)] += 1
print(max(counts))


import sys
sys.setrecursionlimit(1500)
m = int(input())
n = int(input())

def floodFill(matrix, x, y, countAr):
	if x < 0 or y < 0 or x >= len(matrix) or (y >= len(matrix[0])):
		return
	if matrix[x][y] != '1':
		return
	matrix[x][y] = 'x'
	countAr[0] = countAr[0] + 1
	floodFill(matrix, x, y + 1, countAr)
	floodFill(matrix, x + 1, y + 1, countAr)
	floodFill(matrix, x + 1, y, countAr)
	floodFill(matrix, x + 1, y - 1, countAr)
	floodFill(matrix, x, y - 1, countAr)
	floodFill(matrix, x - 1, y - 1, countAr)
	floodFill(matrix, x - 1, y, countAr)
	floodFill(matrix, x - 1, y + 1, countAr)
	return countAr[0]
matrix = []
for i in range(m):
	matrix.append(input().split())
count = 0
arr = []
for i in range(len(matrix)):
	for j in range(len(matrix[i])):
		if matrix[i][j] == '1':
			countAr = [0]
			maxlen = floodFill(matrix, i, j, countAr)
			arr.append(maxlen)
print(max(arr))


def countAt(theMatrix, i, j):
	if i < 0 or j < 0 or i >= len(theMatrix) or (j >= len(theMatrix[0])) or (theMatrix[i][j] == 0):
		return 0
	else:
		count = 1
		theMatrix[i][j] = 0
		deltas = [-1, 0, 1]
		for k in deltas:
			for l in deltas:
				count += countAt(theMatrix, i + k, j + l)
		return count

def findMax(matrix):
	maximum = 0
	for i in range(len(matrix)):
		for j in range(len(matrix[0])):
			count = countAt(matrix, i, j)
			if count > maximum:
				maximum = count
	return maximum
(rows, temp) = (int(input()), input())
theMatrix = []
for i in range(rows):
	theMatrix.append([int(x) for x in input().split()])
print(findMax(theMatrix))


m = int(input())
n = int(input())
field = []
for i in range(0, m):
	field.append(input().split())
res = 0

def search_from(field, i, j):
	res = 1
	field[i][j] = 'X'
	i_combs = [i]
	j_combs = [j]
	if i > 0:
		i_combs.append(i - 1)
	if i < len(field) - 1:
		i_combs.append(i + 1)
	if j > 0:
		j_combs.append(j - 1)
	if j < len(field[0]) - 1:
		j_combs.append(j + 1)
	for k in i_combs:
		for l in j_combs:
			if field[k][l] == '1':
				res += search_from(field, k, l)
	return res
for i in range(0, m):
	for j in range(0, n):
		if field[i][j] == '1':
			res = max(res, search_from(field, i, j))
print(res)


from collections import defaultdict

def max_connected_region_size(g, m, n):
	visited = set()
	regions = defaultdict(set)

	def visit(p, reg):
		visited.add(p)
		regions[reg].add(p)
		for i in [-1, 0, 1]:
			for j in [-1, 0, 1]:
				q = (p[0] + i, p[1] + j)
				if 0 <= q[0] < m and 0 <= q[1] < n:
					if g[q[0]][q[1]] and q not in visited:
						visit(q, reg)
	reg = 0
	stop = False
	for i in range(m):
		for j in range(n):
			p = (i, j)
			if g[i][j] and p not in visited:
				visit(p, reg)
				reg += 1
	return max((len(vs) for vs in regions.values()))
m = int(input())
n = int(input())
g = []
for _ in range(m):
	g.append([int(v.strip()) for v in input().split()])
print(max_connected_region_size(g, m, n))


def startSearch(cood, mati, nSearched):
	tsearch = [cood]
	i = 0
	while i < len(tsearch):
		retted = sSearch(tsearch[i], mati, nSearched)
		nSearched = retted[1]
		for newPoint in retted[0]:
			tsearch.append(newPoint)
		i += 1
	return [i, nSearched]

def sSearch(cood, mati, nSearched):
	toRet = []
	for i in [1, 2, 3, 4, 6, 7, 8, 9]:
		d = [cood[0] + (i - 1) % 3 - 1, cood[1] + (i - 1) // 3 - 1]
		if nSearched[d[0]][d[1]]:
			nSearched[d[0]][d[1]] = 0
			if mati[d[0]][d[1]]:
				toRet.append(d)
	return [toRet, nSearched]
m = int(input())
n = int(input())
mati = [[0 for _ in range(n + 2)]]
for _ in range(m):
	mati.append([0] + [int(i) for i in input().strip().split(' ')] + [0])
mati.append([0 for _ in range(n + 2)])
nSearched = [[1] * len(mati[0]) for _ in range(len(mati))]
maxSize = 0
while sum([sum(i) for i in nSearched]) != 0:
	trigg = 0
	for i in range(len(mati)):
		for j in range(len(mati[0])):
			if nSearched[i][j]:
				nSearched[i][j] = 0
				trigg = 1
				if mati[i][j]:
					retted = startSearch([i, j], mati, nSearched)
					nSearched = retted[1]
					maxSize = max(maxSize, retted[0])
			if trigg:
				break
		if trigg:
			break
print(maxSize)


def BuildGraph(m, n, A):
	graph = {}
	for g in range(m * n):
		graph[g] = []
	for i in range(m):
		for j in range(n):
			if A[i][j] == 1:
				g = i * n + j
				graph[g].append(g)
				n_i = i
				n_j = j + 1
				n_g = n_i * n + n_j
				if n_j < n and A[n_i][n_j] == 1:
					graph[g].append(n_g)
					graph[n_g].append(g)
				n_i = i + 1
				n_j = j + 1
				n_g = n_i * n + n_j
				if n_i < m and n_j < n and (A[n_i][n_j] == 1):
					graph[g].append(n_g)
					graph[n_g].append(g)
				n_i = i + 1
				n_j = j
				n_g = n_i * n + n_j
				if n_i < m and A[n_i][n_j] == 1:
					graph[g].append(n_g)
					graph[n_g].append(g)
				n_i = i + 1
				n_j = j - 1
				n_g = n_i * n + n_j
				if n_i < m and n_j < n and (n_j >= 0) and (A[n_i][n_j] == 1):
					graph[g].append(n_g)
					graph[n_g].append(g)
	for g in range(m * n):
		if len(graph[g]) == 0:
			del graph[g]
	return graph

def iterative_bfs(graph, start, path=[]):
	q = [start]
	while q:
		v = q.pop(0)
		if not v in path:
			path = path + [v]
			q = q + graph[v]
	return path

def FindMaxRegion(m, n, A):
	graph = BuildGraph(m, n, A)
	unseen_nodes = list(graph.keys())
	max_region = 0
	while len(unseen_nodes):
		path = iterative_bfs(graph, unseen_nodes[0])
		if max_region < len(path):
			max_region = len(path)
		for node in path:
			unseen_nodes.remove(node)
	return max_region

def main():
	m = int(input())
	n = int(input())
	A = [[0 for j in range(n)] for i in range(m)]
	for i in range(m):
		row_list = input().split()
		for j in range(n):
			A[i][j] = int(row_list[j])
	print(FindMaxRegion(m, n, A))
main()


import sys
number_of_rows = int(sys.stdin.readline())
number_of_columns = int(sys.stdin.readline())
grid = []
for row in range(number_of_rows):
	row = sys.stdin.readline().strip('\\s\n').split()
	grid.append(row)
path_grid = [[set() for x in range(number_of_columns)] for x in range(number_of_rows)]
overall_max_area = int(0)
for current_row in range(number_of_rows):
	for current_column in range(number_of_columns):
		if grid[current_row][current_column] != '0':
			max_path = set([(current_row, current_column)])
			for last_column in range(current_column - 1, current_column + 2):
				if last_column >= 0 and last_column < number_of_columns:
					max_path = max_path.union(path_grid[current_row - 1][last_column])
			if current_column > 0 and len(path_grid[current_row][current_column - 1]):
				max_path = max_path.union(path_grid[current_row][current_column - 1])
			for last_column in range(0, current_column - 1):
				if len(path_grid[current_row - 1][last_column]):
					difference = path_grid[current_row - 1][last_column].difference(max_path)
					if len(difference) < len(path_grid[current_row - 1][last_column]):
						max_path.update(difference)
			for last_column in range(current_column + 2, number_of_columns):
				if len(path_grid[current_row - 1][last_column]):
					difference = path_grid[current_row - 1][last_column].difference(max_path)
					if len(difference) < len(path_grid[current_row - 1][last_column]):
						max_path.update(difference)
			for last_column in range(0, current_column - 1):
				if len(path_grid[current_row][last_column]):
					difference = path_grid[current_row][last_column].difference(max_path)
					if len(difference) < len(path_grid[current_row][last_column]):
						max_path.update(difference)
			path_grid[current_row][current_column] = max_path
			if len(path_grid[current_row][current_column]) > overall_max_area:
				overall_max_area = len(path_grid[current_row][current_column])
print(overall_max_area)


class Node:

	def __init__(self, x, y):
		self.x = x
		self.y = y
		self.adjacents = []
		self.state = 'white'

	def __repr__(self):
		return '(%d, %d, %s)' % (self.x, self.y, self.state)

	def toKey(self):
		return (self.x, self.y)

	def getAdjacentKeys(self):
		keys = [(x, y) for x in range(self.x - 1, self.x + 2) for y in range(self.y - 1, self.y + 2) if x >= 0 and y >= 0 and (Node(x, y) != self)]
		return keys

	def __eq__(self, other):
		return self.x == other.x and self.y == other.y

	def addAdjacent(self, n):
		if n not in self.adjacents:
			self.adjacents.append(n)

def dfs(node):
	if node.state == 'white':
		node.state = 'gray'
		s = 1
		for adj in node.adjacents:
			s += dfs(adj)
		node.state = 'black'
		return s
	return 0
graph = {}
m = int(input())
n = int(input())
values = [[c.rstrip() for c in input().split(' ')] for r in range(m)]
nodes = [Node(x, y) for x in range(m) for y in range(n) if values[x][y] == '1']
for n in nodes:
	graph[n.toKey()] = n
for n in nodes:
	akeys = n.getAdjacentKeys()
	for ak in akeys:
		if ak in graph:
			n.addAdjacent(graph[ak])
			graph[ak].addAdjacent(n)
totalMax = 0
for n in nodes:
	totalMax = max(totalMax, dfs(n))
print(totalMax)


class Cell:

	def __init__(self, x, y, val):
		self.x = x
		self.y = y
		self.on = val == 1
		self.ischecked = False
		self.neighbors = []

	def set_neighbor(self, cell):
		self.neighbors.append(cell)

	def get_isconnected(self):
		return len(self.neighbors) > 0

	def get_neighbors(self):
		return self.neighbors

	def get_on(self):
		return self.on

	def get_ischecked(self):
		return self.ischecked

	def set_ischecked(self, b):
		self.ischecked = b

	def get_x(self):
		return self.x

	def get_y(self):
		return self.y

class Matrix:

	def __init__(self):
		self.rows = []

	def add_row(self, row):
		self.rows.append(row)

	def get_cell(self, x, y):
		return self.rows[y][x]

	def check_neighbor(self, x, y):
		if x < 0 or x >= len(self.rows[0]):
			return None
		if y < 0 or y >= len(self.rows):
			return None
		if self.rows[y][x].get_on():
			return self.rows[y][x]
		else:
			return None

	def check_if_connected(self, cell):
		if not cell.get_on():
			return False
		x = cell.get_x()
		y = cell.get_y()
		above = self.check_neighbor(x, y - 1)
		if above != None:
			cell.set_neighbor(above)
		tr = self.check_neighbor(x + 1, y - 1)
		if tr != None:
			cell.set_neighbor(tr)
		tl = self.check_neighbor(x - 1, y - 1)
		if tl != None:
			cell.set_neighbor(tl)
		below = self.check_neighbor(x, y + 1)
		if below != None:
			cell.set_neighbor(below)
		br = self.check_neighbor(x + 1, y + 1)
		if br != None:
			cell.set_neighbor(br)
		bl = self.check_neighbor(x - 1, y + 1)
		if bl != None:
			cell.set_neighbor(bl)
		right = self.check_neighbor(x + 1, y)
		if right != None:
			cell.set_neighbor(right)
		left = self.check_neighbor(x - 1, y)
		if left != None:
			cell.set_neighbor(left)
		return len(cell.get_neighbors()) > 0

	def count_region(self, cell, aggregate):
		x = cell.get_x()
		y = cell.get_y()
		if cell.get_ischecked():
			return aggregate
		else:
			aggregate += 1
			cell.set_ischecked(True)
		for n in cell.get_neighbors():
			aggregate = self.count_region(n, aggregate)
		return aggregate

	def get_connected_region(self):
		max_result_count = 0
		for y in range(0, len(self.rows)):
			row = self.rows[y]
			for x in range(0, len(row)):
				cell = row[x]
				self.check_if_connected(cell)
		for y in range(0, len(self.rows)):
			row = self.rows[y]
			for x in range(0, len(row)):
				cell = row[x]
				result = self.count_region(cell, 0)
				if result > max_result_count:
					max_result_count = result
		return max_result_count
rows = int(input())
cols = int(input())
matrix = Matrix()
for i in range(0, rows):
	row = list(map(int, input().split()))
	cell_row = []
	for j in range(0, cols):
		cell = Cell(j, i, row[j])
		cell_row.append(cell)
	matrix.add_row(cell_row)
print(matrix.get_connected_region())


def expand(grid, i, j, target):
	if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])):
		return 0
	elif grid[i][j] == target:
		grid[i][j] = -1
		return 1 + expand(grid, i - 1, j - 1, target) + expand(grid, i - 1, j, target) + expand(grid, i - 1, j + 1, target) + expand(grid, i, j - 1, target) + expand(grid, i, j, target) + expand(grid, i, j + 1, target) + expand(grid, i + 1, j - 1, target) + expand(grid, i + 1, j, target) + expand(grid, i + 1, j + 1, target)
	else:
		return 0

def main():
	m = int(input())
	_ = input()
	grid = []
	for _ in range(m):
		grid.append([int(y) for y in input().split()])
	if len(grid) == 0 or len(grid[0]) == 0:
		return 0
	max_so_far = 0
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			if grid[i][j] > 0:
				max_so_far = max(max_so_far, expand(grid, i, j, grid[i][j]))
	print(max_so_far)
main()


import sys
nrows = int(input())
ncolumns = int(input())
grid = [[int(c) for c in row.split()] for row in sys.stdin.readlines()]

def get_neighbours(coords):
	return [(coords[0] + 1, coords[1]), (coords[0] - 1, coords[1]), (coords[0], coords[1] + 1), (coords[0], coords[1] - 1), (coords[0] + 1, coords[1] + 1), (coords[0] + 1, coords[1] - 1), (coords[0] - 1, coords[1] + 1), (coords[0] - 1, coords[1] - 1)]

def dfs(g, v, discovered):
	size = 1
	for n in get_neighbours(v):
		if n in g and n not in discovered:
			discovered.append(n)
			size = size + dfs(g, n, discovered)
	return size
starting_points = []
for i in range(0, nrows):
	for j in range(0, ncolumns):
		elem = grid[i][j]
		if elem == 1:
			starting_points.append((i, j))
high = 1
for starting_point in starting_points:
	discovered = [starting_point]
	high = max(high, dfs(starting_points, starting_point, discovered))
print(str(high))


from itertools import product

def eat_region(grid, m, n, i, j):

	def is_within_grid(d):
		return d[0] >= 0 and d[1] >= 0 and (d[0] < m) and (d[1] < n)
	neighborhood = map(lambda d: (i + d[0], j + d[1]), product([-1, 0, 1], repeat=2))
	neighborhood = filter(is_within_grid, neighborhood)
	grid[i][j] = 0
	area = 1
	for (next_i, next_j) in neighborhood:
		if grid[next_i][next_j] != 0:
			area += eat_region(grid, m, n, next_i, next_j)
	return area

def max_area(grid, m, n):
	result = 0
	for i in range(m):
		for j in range(n):
			if grid[i][j] != 0:
				result = max(result, eat_region(grid, m, n, i, j))
	return result
m = int(input())
n = int(input())
grid = []
for i in range(m):
	grid.append(list(map(int, input().split())))
print(max_area(grid, m, n))


rows = []
hist = {}

def printarray(ar):
	for x in ar:
		print(x)

def relabel(ar, old, new, maxrow, maxcol):
	for i in range(maxrow):
		x = ar[i]
		for j in range(maxcol):
			if x[j] == old:
				x[j] = new
				hist[old] -= 1
				hist[new] += 1

def printspecial(ar, spec):
	for x in ar:
		str = ''
		for y in x:
			if y == 0:
				xx = '0'
			elif y == spec:
				xx = 'X'
			else:
				xx = '1'
			if len(str):
				str = str + ' ' + xx
			else:
				str = xx
		print(str)

def propogate(rows, hist, m, n, i, j, v):
	r = rows[i][j]
	if r == 0 or r == v:
		return
	if r == 1:
		rows[i][j] = v
		hist[v] += 1
	else:
		relabel(rows, r, v, m, n)
m = int(input().strip())
n = int(input().strip())
indx = 2
for rownum in range(m):
	col = [int(i) for i in input().strip().split()]
	rows.append(col)
for i in range(m):
	mm = i + 1
	for j in range(n):
		v = rows[i][j]
		if v == 1:
			v = indx
			rows[i][j] = v
			hist[indx] = 1
			indx += 1
		if v > 1:
			if j + 1 < n:
				propogate(rows, hist, mm, n, i, j + 1, v)
			if i + 1 < m:
				propogate(rows, hist, mm, n, i + 1, j, v)
				if j + 1 < n:
					propogate(rows, hist, mm, n, i + 1, j + 1, v)
					if rows[i + 1][j + 1] == 1:
						rows[i + 1][j + 1] = v
						hist[v] += 1
				if j - 1 >= 0:
					propogate(rows, hist, mm, n, i + 1, j - 1, v)
	for j in range(n - 1, -1, -1):
		v = rows[i][j]
		if v > 1:
			if j - 1 >= 0:
				propogate(rows, hist, mm, n, i, j - 1, v)
			if i + 1 < m:
				propogate(rows, hist, mm, n, i + 1, j, v)
				if j + 1 < n:
					propogate(rows, hist, mm, n, i + 1, j + 1, v)
				if j - 1 >= 0:
					propogate(rows, hist, mm, n, i + 1, j - 1, v)
maxx = 0
maxi = 0
for x in hist:
	if hist[x] > maxx:
		maxi = x
		maxx = hist[x]
print(maxx)


def in_bounds(grid, i, j):
	return i >= 0 and j >= 0 and (i < len(grid)) and (j < len(grid[0]))

def count_size(i, j, grid, used):
	if not in_bounds(grid, i, j) or used[i][j] or (not grid[i][j]):
		return 0
	count = 1
	used[i][j] = True
	for di in (-1, 0, 1):
		for dj in (-1, 0, 1):
			count += count_size(i + di, j + dj, grid, used)
	return count
(rows, cols) = (int(input()), int(input()))
grid = [[int(j) for j in input().split()] for i in range(rows)]
largest_size = 0
for i in range(rows):
	for j in range(rows):
		used = [[False for j in range(cols)] for i in range(rows)]
		size = count_size(i, j, grid, used)
		if size > largest_size:
			largest_size = size
print(largest_size)


n1 = int(input())
n2 = int(input())
dim = (n1, n2)
cellmatrix = []
for i in range(0, n1):
	cellmatrix.extend([int(i) for i in input().split()])
cellmatrix2 = [i for i in range(len(cellmatrix))]
for i in range(len(cellmatrix)):
	if cellmatrix[i] != 0:
		cellmatrix2[i] = i + 1
	else:
		cellmatrix2[i] = len(cellmatrix) + 1

def indexToCoords(i):
	y = i // dim[1]
	x = i % dim[1]
	return (x, y)

def coordsToIndex(x, y):
	if y >= dim[0]:
		print('y >= dim[0] ', y)
	if x >= dim[1]:
		print('x >= dim[1] ', x)
	return y * dim[1] + x

def getMinAdjacentElement(i):
	minAdjacentElement = len(cellmatrix2) + 1
	(x, y) = indexToCoords(i)
	if x > 0:
		if y > 0:
			j = coordsToIndex(x - 1, y - 1)
			if minAdjacentElement > cellmatrix2[j]:
				minAdjacentElement = cellmatrix2[j]
		j = coordsToIndex(x - 1, y)
		if minAdjacentElement > cellmatrix2[j]:
			minAdjacentElement = cellmatrix2[j]
		if y < dim[0] - 1:
			j = coordsToIndex(x - 1, y + 1)
			if minAdjacentElement > cellmatrix2[j]:
				minAdjacentElement = cellmatrix2[j]
	if y > 0:
		j = coordsToIndex(x, y - 1)
		if minAdjacentElement > cellmatrix2[j]:
			minAdjacentElement = cellmatrix2[j]
	if y < dim[0] - 1:
		j = coordsToIndex(x, y + 1)
		if minAdjacentElement > cellmatrix2[j]:
			minAdjacentElement = cellmatrix2[j]
	if x < dim[1] - 1:
		if y > 0:
			j = coordsToIndex(x + 1, y - 1)
			if minAdjacentElement > cellmatrix2[j]:
				minAdjacentElement = cellmatrix2[j]
		j = coordsToIndex(x + 1, y)
		if minAdjacentElement > cellmatrix2[j]:
			minAdjacentElement = cellmatrix2[j]
		if y < dim[0] - 1:
			j = coordsToIndex(x + 1, y + 1)
			if minAdjacentElement > cellmatrix2[j]:
				minAdjacentElement = cellmatrix2[j]
	return minAdjacentElement
change = True
while change:
	change = False
	for i in range(len(cellmatrix2)):
		if cellmatrix[i] != 0:
			res = min(cellmatrix2[i], getMinAdjacentElement(i))
			if res != cellmatrix2[i]:
				change = True
				cellmatrix2[i] = res
		else:
			pass
hist = {}
for i in range(len(cellmatrix2)):
	if cellmatrix2[i] == len(cellmatrix2) + 1:
		continue
	if cellmatrix2[i] not in hist:
		hist[cellmatrix2[i]] = 0
	hist[cellmatrix2[i]] += 1
print(max(hist.values()))


def ContadorRegiao(matriz, i, j):
	if i >= 0 and i < len(matriz) and (j >= 0) and (j < len(matriz[i])) and (matriz[i][j] == 1):
		matriz[i][j] = 0
		contador = 1
		contador += ContadorRegiao(matriz, i + 1, j)
		contador += ContadorRegiao(matriz, i - 1, j)
		contador += ContadorRegiao(matriz, i, j + 1)
		contador += ContadorRegiao(matriz, i, j - 1)
		contador += ContadorRegiao(matriz, i + 1, j + 1)
		contador += ContadorRegiao(matriz, i + 1, j - 1)
		contador += ContadorRegiao(matriz, i - 1, j + 1)
		contador += ContadorRegiao(matriz, i - 1, j - 1)
		return contador
	return 0

def ContadorMaximoRegiao(matriz):
	contador = 0
	for i in range(len(matriz)):
		for j in range(len(matriz[i])):
			temp = ContadorRegiao(matriz, i, j)
			if temp > contador:
				contador = temp
	return contador
m = int(input())
n = int(input())
matriz = []
for i in range(m):
	matriz.append([])
	matriz[i] = [int(x) for x in input().split()]
print(ContadorMaximoRegiao(matriz))


dirs = ((-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1))
m = int(input())
n = int(input())
grid = [[int(item) for item in input().split()] for rowi in range(m)]

def connected(cell):
	(i, j) = cell
	for dir in dirs:
		(ni, nj) = (i + dir[0], j + dir[1])
		if 0 <= ni < m and 0 <= nj < n and (grid[ni][nj] == 1):
			yield (ni, nj)
queue = [None] * 101
prevqueue = [None] * 101
maxcount = 0
marker = 1
for i in range(m):
	for j in range(n):
		if grid[i][j] != 1:
			continue
		marker += 1
		grid[i][j] = marker
		queue[0] = (i, j)
		curcount = 1
		while queue[0] != None:
			(prevqueue, queue) = (queue, prevqueue)
			pqi = 0
			qi = 0
			while prevqueue[pqi] != None:
				for cell in connected(prevqueue[pqi]):
					grid[cell[0]][cell[1]] = marker
					queue[qi] = cell
					curcount += 1
					qi += 1
				pqi += 1
			queue[qi] = None
		maxcount = max(curcount, maxcount)
print(maxcount)


numrows = int(input())
numcolumns = int(input())
grid = []
checked = []
for i in range(numrows):
	grid.append(list(map(int, input().split())))

def regionsizer(x, y):
	if x < 0 or x >= numrows or y < 0 or (y >= numcolumns) or (grid[x][y] == 0) or ((x, y) in checked):
		return 0
	checked.append((x, y))
	return grid[x][y] + sum([regionsizer(i, j) for i in [x - 1, x, x + 1] for j in [y - 1, y, y + 1]])
answer = 0
for x in range(numrows):
	for y in range(numcolumns):
		if (x, y) not in checked:
			answer = max(answer, regionsizer(x, y))
print(answer)


def Find(G, val):
	for (row, l) in enumerate(G):
		for (col, x) in enumerate(l):
			if x == val:
				return (row, col)
visited = set()

def BFS(G, i, j, m, n):
	q = [Grid[i][j]]
	visit = set()
	while len(q) != 0:
		val = q.pop(0)
		(i, j) = Find(Grid, val)
		if val not in visit:
			visit.add(val)
			visited.add(val)
		if i == m - 1 and j == n - 1:
			q = []
			break
		if i == m - 1:
			if Grid[i][j + 1] != 0 and Grid[i][j + 1] not in visit:
				q.append(Grid[i][j + 1])
			continue
		if j == 0:
			if Grid[i][j + 1] != 0 and Grid[i][j + 1] not in visit:
				q.append(Grid[i][j + 1])
			if Grid[i + 1][j + 1] != 0 and Grid[i + 1][j + 1] not in visit:
				q.append(Grid[i + 1][j + 1])
			if Grid[i + 1][j] != 0 and Grid[i + 1][j] not in visit:
				q.append(Grid[i + 1][j])
			continue
		if j == n - 1:
			if Grid[i + 1][j - 1] != 0 and Grid[i + 1][j - 1] not in visit:
				q.append(Grid[i + 1][j - 1])
			if Grid[i + 1][j] != 0 and Grid[i + 1][j] not in visit:
				q.append(Grid[i + 1][j])
			continue
		if i == 0:
			if Grid[i][j + 1] != 0 and Grid[i][j + 1] not in visit:
				q.append(Grid[i][j + 1])
			if Grid[i + 1][j + 1] != 0 and Grid[i + 1][j + 1] not in visit:
				q.append(Grid[i + 1][j + 1])
			if Grid[i + 1][j] != 0 and Grid[i + 1][j] not in visit:
				q.append(Grid[i + 1][j])
			if Grid[i + 1][j - 1] != 0 and Grid[i + 1][j - 1] not in visit:
				q.append(Grid[i + 1][j - 1])
			if Grid[i][j - 1] != 0 and Grid[i][j - 1] not in visit:
				q.append(Grid[i][j - 1])
			continue
		if Grid[i][j + 1] != 0 and Grid[i][j + 1] not in visit:
			q.append(Grid[i][j + 1])
		if Grid[i + 1][j + 1] != 0 and Grid[i + 1][j + 1] not in visit:
			q.append(Grid[i + 1][j + 1])
		if Grid[i + 1][j] != 0 and Grid[i + 1][j] not in visit:
			q.append(Grid[i + 1][j])
		if Grid[i + 1][j - 1] != 0 and Grid[i + 1][j - 1] not in visit:
			q.append(Grid[i + 1][j - 1])
		if Grid[i][j - 1] != 0 and Grid[i][j - 1] not in visit:
			q.append(Grid[i][j - 1])
		if Grid[i - 1][j] != 0 and Grid[i - 1][j] not in visit:
			q.append(Grid[i - 1][j])
		if Grid[i - 1][j + 1] != 0 and Grid[i - 1][j + 1] not in visit:
			q.append(Grid[i - 1][j + 1])
	return len(visit)
m = int(input())
n = int(input())
Grid = [list(map(int, input().split())) for _ in range(m)]
count = 1
Max = 1
for i in range(m):
	for j in range(n):
		if Grid[i][j] == 1:
			Grid[i][j] = count
			count += 1
for i in range(m):
	for j in range(n):
		if Grid[i][j] != 0 and Grid[i][j] not in visited:
			length = BFS(Grid, i, j, m, n)
			if length > Max:
				Max = length
print(Max)


rows = int(input())
cols = int(input())
M = [[int(n) for n in input().split()] for r in range(rows)]
unvisited = set([(r, c) for r in range(rows) for c in range(cols) if M[r][c] == 1])

def isValid(loc):
	lo = (0, 0)
	hi = (rows, cols)
	for i in range(len(loc)):
		if loc[i] < lo[i] or loc[i] >= hi[i]:
			return False
	return True

def neighbors(loc):
	neighborRows = range(loc[0] - 1, loc[0] + 2)
	neighborCols = range(loc[1] - 1, loc[1] + 2)
	neighborLocs = set(((r, c) for r in neighborRows for c in neighborCols if isValid((r, c)) and M[r][c] == 1))
	neighborLocs.remove(loc)
	return neighborLocs

def dfs(loc):
	count = 1
	unvisited.remove(loc)
	for neighbor in neighbors(loc):
		if neighbor in unvisited:
			count += dfs(neighbor)
	return count
maxSize = 0
while len(unvisited) > 0:
	loc = unvisited.pop()
	unvisited.add(loc)
	ccSize = dfs(loc)
	if ccSize > maxSize:
		maxSize = ccSize
print(maxSize)


from collections import deque
from itertools import product

def bfs(grid, i, j):
	if grid[i][j] == 0:
		return 0
	grid[i][j] = 0
	count = 1
	queue = deque([(i, j)])
	while queue:
		(i, j) = queue.popleft()
		for (i, j) in product((i - 1, i, i + 1), (j - 1, j, j + 1)):
			if i < 0 or i >= len(grid) or j < 0 or (j >= len(grid[0])):
				continue
			if grid[i][j] == 0:
				continue
			count += 1
			grid[i][j] = 0
			queue.append((i, j))
	return count
m = int(input())
n = int(input())
grid = [[int(s) for s in input().split()] for i in range(m)]
print(max((bfs(grid, i, j) for i in range(m) for j in range(n))))


N = int(input())
M = int(input())
board = [[int(j) for j in input().split()] for i in range(N)]
maxcount = 0
mainlist = []
sublist = []
for i in range(N):
	for j in range(M):
		if board[i][j] == 1:
			sublist.append((i, j))
			if i > 0 and board[i - 1][j] == 1:
				sublist.append((i - 1, j))
			if j > 0 and board[i][j - 1] == 1:
				sublist.append((i, j - 1))
			if i < N - 1 and board[i + 1][j] == 1:
				sublist.append((i + 1, j))
			if j < M - 1 and board[i][j + 1] == 1:
				sublist.append((i, j + 1))
			if i > 0 and j > 0 and (board[i - 1][j - 1] == 1):
				sublist.append((i - 1, j - 1))
			if i > 0 and j < M - 1 and (board[i - 1][j + 1] == 1):
				sublist.append((i - 1, j + 1))
			if i < N - 1 and j > 0 and (board[i + 1][j - 1] == 1):
				sublist.append((i + 1, j - 1))
			if i < N - 1 and j < M - 1 and (board[i + 1][j + 1] == 1):
				sublist.append((i + 1, j + 1))
		mainlist.append(sublist)
		sublist = []
i = 0
k = len(mainlist)
while i < k - 1:
	j = i + 1
	while j < k:
		if set(mainlist[i]) & set(mainlist[j]):
			mainlist[i] += mainlist[j]
		j += 1
		k = len(mainlist)
	i += 1
print(max([len(set(i)) for i in mainlist]))


def max_region_size(A, m, n):
	maximum = 0

	def flood_fill(i, j):
		size = 0
		if A[i][j] == 1:
			A[i][j] = 'X'
			size += 1
			size += flood_fill(i - 1, j) if i > 0 else 0
			size += flood_fill(i + 1, j) if i < m - 1 else 0
			size += flood_fill(i, j - 1) if j > 0 else 0
			size += flood_fill(i, j + 1) if j < n - 1 else 0
			size += flood_fill(i - 1, j - 1) if i > 0 and j > 0 else 0
			size += flood_fill(i - 1, j + 1) if i > 0 and j < n - 1 else 0
			size += flood_fill(i + 1, j - 1) if i < m - 1 and j > 0 else 0
			size += flood_fill(i + 1, j + 1) if i < m - 1 and j < n - 1 else 0
		return size
	for i in range(m):
		for j in range(n):
			if A[i][j] == 1:
				maximum = max(flood_fill(i, j), maximum)
	return maximum

def main():
	m = int(input())
	n = int(input())
	A = []
	for _ in range(m):
		A.append([int(i) for i in input().split()])
	print(max_region_size(A, m, n))
main()


from collections import Counter

def _get_neighbors(i, j, k, l):
	for n in (-1, 0, 1):
		for m in (-1, 0, 1):
			(x, y) = (i + n, j + m)
			if 0 <= x < k and 0 <= y < l:
				yield (x, y)

class UF:

	def __init__(self, size):
		self._arr = list(range(size))
		self._sizes = [1 for _ in range(size)]

	def union(self, i, j):
		(roota, rootb) = (self.find(i), self.find(j))
		if roota != rootb:
			self._arr[roota] = rootb
			self._sizes[rootb] += self._sizes[roota]

	def find(self, i):
		while i != self._arr[i]:
			i = self._arr[i]
		return i

	@property
	def max_size(self):
		return max(self._sizes)

def get_max_cc_size(arr, m, n):
	uf = UF(m * n)
	for i in range(m):
		for j in range(n):
			l = i * n + j
			if arr[l] != 1:
				continue
			for (x, y) in _get_neighbors(i, j, m, n):
				k = x * n + y
				if arr[k] == 1:
					uf.union(l, k)
	return uf.max_size
m = int(input())
n = int(input())
arr = []
for _ in range(m):
	line = [int(el) for el in input().split()]
	arr.extend(line)
print(get_max_cc_size(arr, m, n))


(m, n) = map(int, (input(), input()))
mat = []
for _ in range(m):
	mat.append([int(e) for e in input().split()])

def flood_diag(M, x, y, t, r):
	height = len(M)
	width = len(M[0])
	if M[y][x] == t:
		M[y][x] = r
		count[0] += 1
	else:
		return
	if y < height - 1:
		flood_diag(M, x, y + 1, t, r)
	if y > 0:
		flood_diag(M, x, y - 1, t, r)
	if x > 0:
		flood_diag(M, x - 1, y, t, r)
	if x < width - 1:
		flood_diag(M, x + 1, y, t, r)
	if x < width - 1 and y < height - 1:
		flood_diag(M, x + 1, y + 1, t, r)
	if x > 0 and y > 0:
		flood_diag(M, x - 1, y - 1, t, r)
	if x < width - 1 and y > 0:
		flood_diag(M, x + 1, y - 1, t, r)
	if x > 0 and y < height - 1:
		flood_diag(M, x - 1, y + 1, t, r)
counts = []
for y in range(len(mat)):
	for x in range(len(mat[0])):
		if mat[y][x] == 1:
			count = [0]
			flood_diag(mat, x, y, 1, 9)
			counts.append(count[0])
print(max(counts))


rows = int(input())
columns = int(input())
matrix = []
for row in range(0, rows):
	row = [int(i) for i in input().strip().split()]
	matrix.append(row)

def rabbit_hole(count, i, j, array_visited):
	count += 1
	array_visited.append([i, j])
	right = left = top = bottom = diag_tleft = diag_tright = diag_bright = diag_bleft = 0
	if i < rows - 1:
		bottom = matrix[i + 1][j]
		if j != 0:
			diag_bleft = matrix[i + 1][j - 1]
	if j != 0:
		left = matrix[i][j - 1]
		if i != 0:
			diag_tleft = matrix[i - 1][j - 1]
	if i != 0:
		top = matrix[i - 1][j]
	if j < columns - 1:
		right = matrix[i][j + 1]
		if i < rows - 1:
			diag_bright = matrix[i + 1][j + 1]
		if i != 0:
			diag_tright = matrix[i - 1][j + 1]
	if bottom == 1:
		i += 1
		if [i, j] not in array_visited:
			count = rabbit_hole(count, i, j, array_visited)
		i -= 1
	if top == 1:
		i -= 1
		if [i, j] not in array_visited:
			count = rabbit_hole(count, i, j, array_visited)
		i += 1
	if left == 1:
		j -= 1
		if [i, j] not in array_visited:
			count = rabbit_hole(count, i, j, array_visited)
		j += 1
	if right == 1:
		j += 1
		if [i, j] not in array_visited:
			count = rabbit_hole(count, i, j, array_visited)
		j -= 1
	if diag_tright == 1:
		i -= 1
		j += 1
		if [i, j] not in array_visited:
			count = rabbit_hole(count, i, j, array_visited)
		i += 1
		j -= 1
	if diag_bright == 1:
		i += 1
		j += 1
		if [i, j] not in array_visited:
			count = rabbit_hole(count, i, j, array_visited)
		i -= 1
		j -= 1
	if diag_tleft == 1:
		i -= 1
		j -= 1
		if [i, j] not in array_visited:
			count = rabbit_hole(count, i, j, array_visited)
		i += 1
		j += 1
	if diag_bleft == 1:
		i += 1
		j -= 1
		if [i, j] not in array_visited:
			count = rabbit_hole(count, i, j, array_visited)
		i -= 1
		j += 1
	return count
max_count = 0
for (i, row) in enumerate(matrix):
	for (j, element) in enumerate(row):
		if element == 0:
			rabbit_count = 0
			next
		else:
			array_been = []
			rabbit_count = rabbit_hole(0, i, j, array_been)
		if rabbit_count > max_count:
			max_count = rabbit_count
print(max_count)


def cell(l, m, n, i, j):
	if i < 0 or j < 0 or i == m or (j == n) or (l[i][j] == 0) or (l[i][j] == 2):
		return 0
	c = 0
	if l[i][j] == 1:
		c += 1
		l[i][j] = 2
	c += cell(l, m, n, i - 1, j - 1)
	c += cell(l, m, n, i + 1, j + 1)
	c += cell(l, m, n, i - 1, j + 1)
	c += cell(l, m, n, i + 1, j - 1)
	c += cell(l, m, n, i, j - 1)
	c += cell(l, m, n, i, j + 1)
	c += cell(l, m, n, i - 1, j)
	c += cell(l, m, n, i + 1, j)
	return c

def mat(l, m, n):
	maximum = 0
	for i in range(m):
		for j in range(n):
			c = cell(l, m, n, i, j)
			if c > maximum:
				maximum = c
	print(maximum)

def main():
	m = int(input())
	n = int(input())
	l = []
	for i in range(m):
		l2 = list(map(int, input().split()))
		l.append(l2)
	mat(l, m, n)
main()


def load(fn):
	if fn is not None:
		f = open(fn)
		rows_count = int(f.readline())
		cols_count = int(f.readline())
		lines = f.readlines()
		cells = [[int(c) for c in line.split()] for line in lines]
		print(cells)
		return (rows_count, cols_count, cells)
	else:
		rows_count = int(input())
		cols_count = int(input())
		cells = []
		for i in range(rows_count):
			cells.append([int(c) for c in input().split()])
		return (rows_count, cols_count, cells)

def find_one(rows_count, cols_count, cells):
	for i in range(rows_count):
		for j in range(cols_count):
			if cells[i][j] == 1:
				return (i, j)
	return (-1, -1)

def calc_size(rows_count, cols_count, cells, i, j):
	count = 0
	if cells[i][j] == 0:
		return count
	cells[i][j] = 0
	count += 1
	if j > 0:
		count += calc_size(rows_count, cols_count, cells, i, j - 1)
		if i > 0:
			count += calc_size(rows_count, cols_count, cells, i - 1, j - 1)
	if j < cols_count - 1:
		count += calc_size(rows_count, cols_count, cells, i, j + 1)
		if i < rows_count - 1:
			count += calc_size(rows_count, cols_count, cells, i + 1, j + 1)
	if i > 0:
		count += calc_size(rows_count, cols_count, cells, i - 1, j)
		if j < cols_count - 1:
			count += calc_size(rows_count, cols_count, cells, i - 1, j + 1)
	if i < rows_count - 1:
		count += calc_size(rows_count, cols_count, cells, i + 1, j)
		if j > 0:
			count += calc_size(rows_count, cols_count, cells, i + 1, j - 1)
	return count

def run(fn):
	(rows_count, cols_count, cells) = load(fn)
	(i, j) = find_one(rows_count, cols_count, cells)
	size = 0
	while i >= 0:
		s = calc_size(rows_count, cols_count, cells, i, j)
		size = s if s > size else size
		(i, j) = find_one(rows_count, cols_count, cells)
	return size
print(run(None))


from fileinput import input

def find():
	lines = input()
	m = [int(x) for x in lines[0].strip().split()][0]
	n = [int(x) for x in lines[1].strip().split()][0]
	a = []
	for i in range(2, m + 2):
		a.append([int(x) for x in lines[i].strip().split()])
	res = 0
	for j in range(m):
		for k in range(n):
			tmp = [0]
			dfs(a, j, k, tmp)
			res = max(res, tmp[0])
	print(res)

def dfs(a, j, k, val):
	(m, n) = (len(a), len(a[0]))
	if a[j][k] == 0 or a[j][k] == 2:
		return
	a[j][k] = 2
	val[0] += 1
	if j - 1 >= 0 and k - 1 >= 0:
		dfs(a, j - 1, k - 1, val)
	if j - 1 >= 0:
		dfs(a, j - 1, k, val)
	if j - 1 > 0 and k + 1 < n:
		dfs(a, j - 1, k + 1, val)
	if k - 1 >= 0:
		dfs(a, j, k - 1, val)
	if k + 1 < n:
		dfs(a, j, k + 1, val)
	if j + 1 < m and k - 1 >= 0:
		dfs(a, j + 1, k - 1, val)
	if j + 1 < m:
		dfs(a, j + 1, k, val)
	if j + 1 < m and k + 1 < n:
		dfs(a, j + 1, k, val)
find()


def get_depth(grid, colors, stack):
	maxregion = 0
	for i in range(0, rows):
		for j in range(0, columns):
			if grid[i][j] and colors[i][j] == 0:
				global currentMax
				currentMax = 0
				cell = Gridcell(i, j)
				stack.append(cell)
				regioncount = dfs(grid, colors, stack)
				if regioncount > maxregion:
					maxregion = regioncount
	return maxregion

def dfs(grid, colors, stack):
	while stack:
		cell = stack.pop()
		i = cell.row
		j = cell.column
		colors[cell.row][cell.column] = -1
		global currentMax
		currentMax += 1
		if has_diag_right(grid, i, j, colors):
			cell = Gridcell(i + 1, j + 1)
			stack.append(cell)
			dfs(grid, colors, stack)
		if has_diag_left(grid, i, j, colors):
			cell = Gridcell(i + 1, j - 1)
			stack.append(cell)
			dfs(grid, colors, stack)
		if has_right(grid, i, j, colors):
			cell = Gridcell(i, j + 1)
			stack.append(cell)
			dfs(grid, colors, stack)
		if has_left(grid, i, j, colors):
			cell = Gridcell(i, j - 1)
			stack.append(cell)
			dfs(grid, colors, stack)
		if has_diag_up_left(grid, i, j, colors):
			cell = Gridcell(i - 1, j - 1)
			stack.append(cell)
			dfs(grid, colors, stack)
		if has_diag_up_right(grid, i, j, colors):
			cell = Gridcell(i - 1, j + 1)
			stack.append(cell)
			dfs(grid, colors, stack)
		if has_up(grid, i, j, colors):
			cell = Gridcell(i - 1, j)
			stack.append(cell)
			dfs(grid, colors, stack)
		if has_down(grid, i, j, colors):
			cell = Gridcell(i + 1, j)
			stack.append(cell)
			dfs(grid, colors, stack)
	colors[cell.row][cell.column] = 1
	return currentMax

def has_diag_right(grid, x, y, colors):
	if x + 1 < rows:
		if y + 1 < columns:
			return grid[x + 1][y + 1] == 1 and colors[x + 1][y + 1] == 0
	return False

def has_diag_left(grid, x, y, colors):
	if x + 1 < rows:
		if y - 1 >= 0:
			return grid[x + 1][y - 1] == 1 and colors[x + 1][y - 1] == 0
	return False

def has_diag_up_left(grid, x, y, colors):
	if x - 1 >= 0 and y - 1 >= 0:
		return grid[x - 1][y - 1] == 1 and colors[x - 1][y - 1] == 0
	return False

def has_diag_up_right(grid, x, y, colors):
	if x - 1 >= 0 and y + 1 < columns:
		return grid[x - 1][y + 1] == 1 and colors[x - 1][y + 1] == 0
	return False

def has_up(grid, x, y, colors):
	if x - 1 >= 0:
		return grid[x - 1][y] == 1 and colors[x - 1][y] == 0
	return False

def has_down(grid, x, y, colors):
	if x + 1 < rows:
		return grid[x + 1][y] == 1 and colors[x + 1][y] == 0
	return False

def has_right(grid, x, y, colors):
	if y + 1 < columns:
		return grid[x][y + 1] == 1 and colors[x][y + 1] == 0
	return False

def has_left(grid, x, y, colors):
	if y - 1 >= 0:
		return grid[x][y - 1] == 1 and colors[x][y - 1] == 0
	return False
rows = int(input())
columns = int(input())
currentMax = 0
grid = []
colors = []
stack = []

class Gridcell:

	def __init__(self, row, column):
		self.row = row
		self.column = column
for i in range(rows):
	line = input()
	grid.append(list(map(int, line.split())))
colors = [[0 for x in range(columns)] for x in range(rows)]
print(get_depth(grid, colors, stack))


m = int(input())
n = int(input())
a = []
for k in range(m):
	a.append([int(i) for i in input().split(' ')])
c = []
for k in range(m):
	c.append([-1 for j in range(n)])
cc = 1
maxc = 0

def adj(i, j):
	x = []
	for (k, l) in [[i - 1, j - 1], [i - 1, j], [i - 1, j + 1], [i, j - 1], [i, j + 1], [i + 1, j - 1], [i + 1, j], [i + 1, j + 1]]:
		if k < 0 or k >= m or l < 0 or (l >= n):
			continue
		if a[k][l] == 1 and c[k][l] == -1:
			x.append([k, l])
	return x

def dfs(i, j):
	count = 1
	c[i][j] = cc
	x = adj(i, j)
	if x != None:
		for (k, l) in x:
			if c[k][l] == -1:
				count += dfs(k, l)
	return count
for i in range(m):
	for j in range(n):
		if a[i][j] == 0:
			c[i][j] = 0
			continue
		if c[i][j] == -1:
			cc += 1
			nn = dfs(i, j)
			if nn > maxc:
				maxc = nn
print(maxc)


def visit(matrix, row, col):
	if row < 0 or row >= len(matrix):
		return 0
	if col < 0 or col >= len(matrix[0]):
		return 0
	if matrix[row][col] is 0:
		return 0
	matrix[row][col] = 0
	return 1 + visit(matrix, row - 1, col) + visit(matrix, row + 1, col) + visit(matrix, row, col - 1) + visit(matrix, row, col + 1) + visit(matrix, row + 1, col + 1) + visit(matrix, row + 1, col - 1) + visit(matrix, row - 1, col + 1) + visit(matrix, row - 1, col - 1)
rows = int(input().strip())
columns = int(input().strip())
matrix = []
for i in range(rows):
	row = [int(x) for x in input().strip().split()]
	matrix.append(row)
best = 0
for row in range(rows):
	for col in range(columns):
		val = visit(matrix, row, col)
		if val > best:
			best = val
print(best)


from collections import Counter

class Graph:
	v = 0
	e = 0

	def __init__(self, V):
		self.v = V
		self.adj = [[] for _ in range(V)]

	def addEdge(self, V, W):
		self.adj[V].append(W)
		self.e = self.e + 1

	def V(self):
		return self.v

	def E(self):
		return self.e

class CCClass:
	marked = []
	id = []
	count = 0
	idmax = []

	def __init__(self, graph):
		self.marked = [False] * graph.V()
		self.id = [None] * graph.V()
		idd = 0
		for a in range(graph.V()):
			if self.marked[a] == False:
				if graph.adj[a] != []:
					self.id[a] = idd
				self.cc(graph, a, idd)
				idd = idd + 1
				self.count = self.count + 1

	def Count(self):
		return self.count

	def cc(self, graph, s, idd):
		self.marked[s] = True
		for v in graph.adj[s]:
			if self.marked[v] == False:
				self.id[v] = idd
				self.cc(graph, v, idd)

def invalid(row, col, rowDim, colDim):
	return row < 0 or col < 0 or row >= rowDim or (col >= colDim)
row = int(input())
col = int(input())
array = [[0 for i in range(col)] for j in range(row)]
for i in range(row):
	array[i] = [int(y) for y in input().split()]
g = Graph(row * col)
for i in range(row):
	start = i * col
	for y in range(col):
		if array[i][y] == 0:
			continue
		if invalid(i - 1, y, row, col) == False and array[i - 1][y] == 1:
			g.addEdge(start + y, start + y - col)
		if invalid(i + 1, y, row, col) == False and array[i + 1][y] == 1:
			g.addEdge(start + y, start + y + col)
		if invalid(i, y - 1, row, col) == False and array[i][y - 1] == 1:
			g.addEdge(start + y, start + y - 1)
		if invalid(i, y + 1, row, col) == False and array[i][y + 1] == 1:
			g.addEdge(start + y, start + y + 1)
		if invalid(i - 1, y - 1, row, col) == False and array[i - 1][y - 1] == 1:
			g.addEdge(start + y, start + y - (col + 1))
		if invalid(i + 1, y - 1, row, col) == False and array[i + 1][y - 1] == 1:
			g.addEdge(start + y, start + y + col - 1)
		if invalid(i - 1, y + 1, row, col) == False and array[i - 1][y + 1] == 1:
			g.addEdge(start + y, start + y - (col - 1))
		if invalid(i + 1, y + 1, row, col) == False and array[i + 1][y + 1] == 1:
			g.addEdge(start + y, start + y + col + 1)
ccc = CCClass(g)
c = Counter((i for i in ccc.id if i != None))
if len(c) == 0:
	print('1')
else:
	print(max(c.values()))


m = int(input())
n = int(input())
matrix = []
visited = []
for _ in range(m):
	matrix.append(list(map(int, input().split(' '))))
	visited.append([False] * n)

def countCluster(x, y):
	if x < 0 or x >= len(matrix):
		return 0
	if y < 0 or y >= len(matrix[0]):
		return 0
	if visited[x][y] == True:
		return 0
	if matrix[x][y] == 0:
		visited[x][y] = True
		return 0
	else:
		visited[x][y] = True
		res = 1 + countCluster(x - 1, y - 1) + countCluster(x, y - 1) + countCluster(x + 1, y - 1) + countCluster(x - 1, y) + countCluster(x, y) + countCluster(x + 1, y) + countCluster(x - 1, y + 1) + countCluster(x, y + 1) + countCluster(x + 1, y + 1)
		return res
biggest = 0
for (x, row) in enumerate(matrix):
	for (y, cell) in enumerate(row):
		size = countCluster(x, y)
		if size > biggest:
			biggest = size
print(biggest)


def getSizeOfConnectedRegion(row, col, v, A):
	if A[row][col] == 0:
		return 0
	if A[row][col] > 1:
		return 0
	sum = 1
	A[row][col] = v
	for i in range(row - 1, row + 2):
		for j in range(col - 1, col + 2):
			if i >= 0 and i < len(A) and (j >= 0) and (j < len(A[0])):
				sum += getSizeOfConnectedRegion(i, j, v, A)
	return sum
rows = int(input())
cols = int(input())
A = [[int(x) for x in input().split()] for y in range(rows)]
mx = -1
i = 1
for r in range(rows):
	for c in range(cols):
		i += 1
		temp = getSizeOfConnectedRegion(r, c, i, A)
		if temp > mx:
			mx = temp
print(mx)


def floodFill(grid, r, c, rows, cols):
	region = set()
	toFill = set()
	toFill.add((r, c))
	while toFill:
		(r, c) = toFill.pop()
		region.add((r, c))
		if r > 0:
			if grid[r - 1][c] and (r - 1, c) not in region:
				toFill.add((r - 1, c))
			if c > 0 and grid[r - 1][c - 1] and ((r - 1, c - 1) not in region):
				toFill.add((r - 1, c - 1))
			if c < cols - 1 and grid[r - 1][c + 1] and ((r - 1, c + 1) not in region):
				toFill.add((r - 1, c + 1))
		if r < rows - 1:
			if grid[r + 1][c] and (r + 1, c) not in region:
				toFill.add((r + 1, c))
			if c > 0 and grid[r + 1][c - 1] and ((r + 1, c - 1) not in region):
				toFill.add((r + 1, c - 1))
			if c < cols - 1 and grid[r + 1][c + 1] and ((r + 1, c + 1) not in region):
				toFill.add((r + 1, c + 1))
		if c > 0 and grid[r][c - 1] and ((r, c - 1) not in region):
			toFill.add((r, c - 1))
		if c < cols - 1 and grid[r][c + 1] and ((r, c + 1) not in region):
			toFill.add((r, c + 1))
	return region

def findLargestRegion(rows, cols, grid):
	inRegion = set()
	regionEntries = []
	for r in range(rows):
		for c in range(cols):
			if grid[r][c] and (r, c) not in inRegion:
				region = floodFill(grid, r, c, rows, cols)
				inRegion.update(region)
				regionEntries.append(len(region))
	return sorted(regionEntries, reverse=True)[0]
rows = int(input())
cols = int(input())
grid = []
for i in range(rows):
	grid.append([int(x) for x in input().split()])
print(findLargestRegion(rows, cols, grid))


def find_connections(rows, cols, matrix):
	(graph, nodes_tovisit) = create_graph(rows, cols, matrix)
	nodes_visited = {}
	longest_len = 0
	for (row, col) in nodes_tovisit:
		if (row, col) not in nodes_visited:
			nodes_visited[row, col] = 1
		else:
			continue
		curr_len = 1
		curr_nodes = []
		curr_nodes.extend(graph[row, col])
		for (i, j) in curr_nodes:
			if (i, j) in nodes_visited:
				continue
			curr_len += 1
			nodes_visited[i, j] = 1
			curr_nodes.extend(graph[i, j])
		if curr_len > longest_len:
			(longest_len, curr_len) = (curr_len, 0)
	return longest_len

def create_graph(rows, cols, matrix):
	for row in matrix:
		row.insert(0, 0)
		row.append(0)
	new_row = [0] * (cols + 2)
	matrix.append(new_row)
	matrix.insert(0, new_row)
	graph = {}
	nodes_tovisit = []
	for i in range(1, rows + 1):
		for j in range(1, cols + 1):
			if matrix[i][j] == 1:
				nodes_tovisit.append((i, j))
				if (i, j) not in graph:
					graph[i, j] = []
				if matrix[i + 1][j] == 1:
					graph[i, j].append((i + 1, j))
					if (i + 1, j) in graph:
						graph[i + 1, j].append((i, j))
					else:
						graph[i + 1, j] = [(i, j)]
				if matrix[i][j + 1] == 1:
					graph[i, j].append((i, j + 1))
					if (i, j + 1) in graph:
						graph[i, j + 1].append((i, j))
					else:
						graph[i, j + 1] = [(i, j)]
				if matrix[i + 1][j + 1] == 1:
					graph[i, j].append((i + 1, j + 1))
					if (i + 1, j + 1) in graph:
						graph[i + 1, j + 1].append((i, j))
					else:
						graph[i + 1, j + 1] = [(i, j)]
				if matrix[i + 1][j - 1] == 1:
					graph[i, j].append((i + 1, j - 1))
					if (i + 1, j - 1) in graph:
						graph[i + 1, j - 1].append((i, j))
					else:
						graph[i + 1, j - 1] = [(i, j)]
	return (graph, nodes_tovisit)

def main():
	rows = int(input().strip())
	cols = int(input().strip())
	matrix = []
	for i in range(rows):
		matrix.append([int(i) for i in input().strip().split(' ')])
	print(find_connections(rows, cols, matrix))
main()


def dfs(G, V, i, j, M, N):
	if i < 0 or j < 0 or i >= M or (j >= N) or V[i][j] or (not G[i][j]):
		return 0
	V[i][j] = True
	return 1 + dfs(G, V, i - 1, j, M, N) + dfs(G, V, i + 1, j, M, N) + dfs(G, V, i, j - 1, M, N) + dfs(G, V, i, j + 1, M, N) + dfs(G, V, i - 1, j - 1, M, N) + dfs(G, V, i + 1, j + 1, M, N) + dfs(G, V, i + 1, j - 1, M, N) + dfs(G, V, i - 1, j + 1, M, N)
(M, N) = (int(input()), int(input()))
G = [[int(x) for x in input().split()] for y in range(M)]
V = [[False] * N for x in range(M)]
ret = 0
for i in range(M):
	for j in range(N):
		if G[i][j] and (not V[i][j]):
			ret = max(ret, dfs(G, V, i, j, M, N))
print(ret)


class ConnectedCellInGrid:

	def __init__(self, arr, nb_row, nb_column):
		self.arr = arr
		self.nb_row = nb_row
		self.nb_column = nb_column
		self.max = 0
		self.count = 0
		self.stack = []

	def look_Down(self, current_y, current_x):
		i = 0
		if current_y + 1 < nb_row and arr[current_y + 1][current_x] == 1:
			self.stack.append([current_y + 1, current_x])
			self.arr[current_y + 1][current_x] = 'X'
			self.count += 1

	def look_up(self, current_y, current_x):
		i = 0
		if current_y - 1 > 0 and arr[current_y - 1][current_x] == 1:
			self.stack.append([current_y - 1, current_x])
			self.arr[current_y - 1][current_x] = 'X'
			self.count += 1

	def look_right(self, current_y, current_x):
		i = 0
		if current_x + 1 < nb_column and arr[current_y][current_x + 1] == 1:
			self.stack.append([current_y, current_x + 1])
			self.arr[current_y][current_x + 1] = 'X'
			self.count += 1

	def look_diag(self, current_y, current_x):
		i = 0
		if current_x + 1 < nb_column and current_y + 1 < nb_row and (arr[current_y + 1][current_x + 1] == 1):
			self.stack.append([current_y + 1, current_x + 1])
			self.arr[current_y + 1][current_x + 1] = 'X'
			self.count += 1
		if current_x - 1 >= 0 and current_y + 1 < nb_row and (arr[current_y + 1][current_x - 1] == 1):
			self.stack.append([current_y + 1, current_x - 1])
			self.arr[current_y + 1][current_x - 1] = 'X'
			self.count += 1
		if current_x - 1 >= 0 and current_y - 1 >= 0 and (arr[current_y - 1][current_x - 1] == 1):
			self.stack.append([current_y - 1, current_x - 1])
			self.arr[current_y - 1][current_x - 1] = 'X'
			self.count += 1
		if current_x + 1 < nb_column and current_y - 1 >= 0 and (arr[current_y - 1][current_x + 1] == 1):
			self.stack.append([current_y - 1, current_x + 1])
			self.arr[current_y - 1][current_x + 1] = 'X'
			self.count += 1

	def look_left(self, current_y, current_x):
		i = 0
		if current_x - 1 >= 0 and arr[current_y][current_x - 1] == 1:
			self.stack.append([current_y, current_x - 1])
			self.arr[current_y][current_x - 1] = 'X'
			self.count += 1

	def nice_print(self):
		for i in range(nb_row):
			j = 0
			for j in range(nb_column):
				print(self.arr[i][j], end=' ')
			print()

	def find_connected_cell(self):
		for i in range(nb_row):
			j = 0
			for j in range(nb_column):
				if self.arr[i][j] == 1:
					self.count += 1
					self.arr[i][j] = 'X'
					self.look_Down(i, j)
					self.look_right(i, j)
					self.look_left(i, j)
					self.look_up(i, j)
					self.look_diag(i, j)
					while len(self.stack) != 0:
						a = self.stack.pop(0)
						self.look_Down(a[0], a[1])
						self.look_right(a[0], a[1])
						self.look_left(a[0], a[1])
						self.look_up(a[0], a[1])
						self.look_diag(a[0], a[1])
					if self.count > self.max:
						self.max = self.count
					self.count = 0
		print(self.max)
nb_row = int(input())
nb_column = int(input())
arr = []
for i in range(nb_row):
	line = input()
	a = list(map(int, line.split()))
	arr.append(a)
c = ConnectedCellInGrid(arr, nb_row, nb_column)
c.find_connected_cell()


from collections import defaultdict, deque

def parse_grid(grid, m, n):
	g = defaultdict(list)
	dxy = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
	for i in range(m):
		for j in range(n):
			if grid[i][j] == 1:
				g[i, j] = []
				for (x, y) in dxy:
					if 0 <= x + i < m and 0 <= y + j < n and (grid[x + i][y + j] == 1):
						g[i, j].append((x + i, y + j))
	return g

def bfs(g, s):
	visited = set()
	q = deque([s])
	while q:
		v = q.popleft()
		visited.add(v)
		for adj in g[v]:
			if adj not in visited and adj not in q:
				q.append(adj)
	return visited

def con_components(g):
	visited = set()
	components = []
	for s in g.keys():
		if s not in visited:
			nodes = bfs(g, s)
			visited |= nodes
			components.append(nodes)
	return components
m = int(input())
n = int(input())
grid = []
for _ in range(m):
	grid.append(list(map(int, input().split())))
g = parse_grid(grid, m, n)
cc = con_components(g)
print(max(map(len, cc)))


def connected_cells(mat):
	visited = set()
	max_count = 0
	for (i, rows) in enumerate(mat):
		for (j, col) in enumerate(rows):
			if col and (i, j) not in visited:
				max_count = max(max_count, dfs(mat, visited, (i, j)))
	return max_count
edges = [(0, 1), (1, 0), (1, 1), (0, -1), (-1, 0), (-1, -1), (-1, 1), (1, -1)]

def dfs(mat, visited, start):
	stack = [start]
	count = 0
	while stack:
		cur = stack.pop()
		visited.add(cur)
		count += 1
		for edge in edges:
			nxt = tuple(map(sum, zip(edge, cur)))
			if len(mat) > nxt[0] >= 0 and len(mat[0]) > nxt[1] >= 0 and mat[nxt[0]][nxt[1]] and (nxt not in visited) and (nxt not in stack):
				stack.append(nxt)
	return count
n = int(input())
m = int(input())
mat = []
for i in range(n):
	mat.append(list(map(int, input().split(' '))))
print(connected_cells(mat))


def get_matrix(rows):
	matrix = []
	for i in range(0, rows):
		matrix.append(list(map(int, input().split())))
	return matrix

def get_region_size(row, col, matrix, value=None):
	size = 0
	if col < 0 or col >= len(matrix[0]) or row < 0 or (row >= len(matrix)):
		return size
	value = matrix[row][col] if value == None else value
	if matrix[row][col] == value:
		matrix[row][col] = 2
		size += 1
		for row_off in range(-1, 2):
			for col_off in range(-1, 2):
				if row_off == 0 and col_off == 0:
					continue
				size += get_region_size(row + row_off, col + col_off, matrix, value)
	return size
max_size = 0
rows = int(input())
cols = int(input())
matrix = get_matrix(rows)
for i in range(0, rows):
	for j in range(0, cols):
		if matrix[i][j] == 1:
			max_size = max(max_size, get_region_size(i, j, matrix))
print(max_size)


class Solution(object):

	def __init__(self):
		self.max = -1
		self.cur_area = 0
		self.dirs = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]

	def solve(self, cipher):
		(m, n, mat) = cipher
		visited = [[False for _ in range(n)] for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if not visited[i][j] and mat[i][j] == 1:
					self.cur_area = 0
					self.dfs(visited, mat, i, j, m, n)
		return self.max

	def dfs(self, visited, mat, i, j, m, n):
		visited[i][j] = True
		self.cur_area += 1
		self.max = max(self.max, self.cur_area)
		for dir in self.dirs:
			i1 = i + dir[0]
			j1 = j + dir[1]
			if 0 <= i1 < m and 0 <= j1 < n and (not visited[i1][j1]) and (mat[i1][j1] == 1):
				self.dfs(visited, mat, i1, j1, m, n)
import sys
solution = Solution()
m = int(input())
n = int(input())
mat = []
for i in range(m):
	mat.append([int(i) for i in input().split()])
cipher = (m, n, mat)
s = solution.solve(cipher)
print(s)


import sys
import collections
m = int(sys.stdin.readline())
n = int(sys.stdin.readline())
matrix = [[] for x in range(m)]
roots = [[] for x in range(m)]

def root(i, j):
	if roots[i][j]:
		(m, n) = roots[i][j]
		if (m, n) == (i, j):
			return (i, j)
		else:
			(m, n) = root(m, n)
			roots[i][j] = (m, n)
			return (m, n)
	return none

def print_roots():
	for row in roots:
		for root in row:
			print(' {} '.format(root), end='')
		print()
for i in range(m):
	row = [int(X) for X in sys.stdin.readline().split()]
	for (j, x) in enumerate(row):
		matrix[i].append(x)
		root_ = None
		if x:
			if j > 0 and matrix[i][j - 1]:
				root_ = root(i, j - 1)
			if j > 0 and i > 0 and matrix[i - 1][j - 1]:
				if root_:
					(a, b) = root(i - 1, j - 1)
					roots[a][b] = root_
				else:
					root_ = root(i - 1, j - 1)
			if i > 0 and matrix[i - 1][j]:
				if root_:
					(a, b) = root(i - 1, j)
					roots[a][b] = root_
				else:
					root_ = root(i - 1, j)
			if j < n - 1 and i > 0 and matrix[i - 1][j + 1]:
				if root_:
					(a, b) = root(i - 1, j + 1)
					roots[a][b] = root_
				else:
					root_ = root(i - 1, j + 1)
			root_ = root_ if root_ else (i, j)
		roots[i].append(root_)
counts = collections.defaultdict(int)
for row in roots:
	for (i, j) in [root_ for root_ in row if root_]:
		(m, n) = root(i, j)
		counts[m, n] += 1
print(max(counts.values()))


def countCells(A, i, j, v, r, c):
	if v[i][j] == 1:
		return 0
	if A[i][j] == '0':
		return 0
	v[i][j] = 1
	acc = 1
	if i + 1 < r:
		acc += countCells(A, i + 1, j, v, r, c)
	if i - 1 >= 0:
		acc += countCells(A, i - 1, j, v, r, c)
	if j + 1 < c:
		acc += countCells(A, i, j + 1, v, r, c)
	if j - 1 >= 0:
		acc += countCells(A, i, j - 1, v, r, c)
	if i - 1 >= 0 and j + 1 < c:
		acc += countCells(A, i - 1, j + 1, v, r, c)
	if i - 1 >= 0 and j - 1 >= 0:
		acc += countCells(A, i - 1, j - 1, v, r, c)
	if i + 1 < r and j + 1 < c:
		acc += countCells(A, i + 1, j + 1, v, r, c)
	if i + 1 < r and j - 1 >= 0:
		acc += countCells(A, i + 1, j - 1, v, r, c)
	return acc

def largestRegion(A, v, r, c):
	l = 0
	for i in range(r):
		for j in range(c):
			if v[i][j] == 0:
				acc = countCells(A, i, j, v, r, c)
			if acc > l:
				l = acc
	return l
r = int(input())
c = int(input())
A = []
v = []
(i, j) = (0, 0)
while i < r:
	A.append(input().split())
	i += 1
while j < r:
	v.append([0 for i in range(c)])
	j += 1
large = largestRegion(A, v, r, c)
print(large)


def dfs_mat(i, j, m, n, A, A_tried):
	val = 1
	A_tried[i][j] = 1
	row_ind_min = -1
	row_ind_max = 1
	if i == 0:
		row_ind_min = 0
	elif i == m - 1:
		row_ind_max = 0
	col_ind_min = -1
	col_ind_max = 1
	if j == 0:
		col_ind_min = 0
	elif j == n - 1:
		col_ind_max = 0
	for row_ind in range(row_ind_min, row_ind_max + 1):
		for col_ind in range(col_ind_min, col_ind_max + 1):
			if (row_ind != 0 or col_ind != 0) and A[i + row_ind][j + col_ind] == 1 and (A_tried[i + row_ind][j + col_ind] == 0):
				val += dfs_mat(i + row_ind, j + col_ind, m, n, A, A_tried)
	return val
m = int(input())
n = int(input())
A = []
A_left = []
for i in range(m):
	row_tmp = input().split()
	for j in range(n):
		row_tmp[j] = int(row_tmp[j])
	A.append(row_tmp)
A_tried = [[0 for j in range(n)] for i in range(m)]
max_cell = 0
for i in range(m):
	for j in range(n):
		if A[i][j] == 1 and A_tried[i][j] == 0:
			tmp_cell = dfs_mat(i, j, m, n, A, A_tried)
			if max_cell < tmp_cell:
				max_cell = tmp_cell
print(max_cell)


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

def solve(grid, m, n):
	delta_x = [0, 1, 1, 1, 0, -1, -1, -1]
	delta_y = [1, 1, 0, -1, -1, -1, 0, 1]
	delta = list(zip(delta_x, delta_y))
	max_count = 0
	visited = [[False] * n for _ in range(m)]
	for i in range(m):
		for j in range(n):
			if grid[i][j] == 1 and (not visited[i][j]):
				visited[i][j] = True
				count = 1
				queue = [(i, j)]
				while queue:
					next_level = []
					for (x, y) in queue:
						for (dx, dy) in delta:
							(new_x, new_y) = (x + dx, y + dy)
							if within_bounds(new_x, new_y, m, n) and (not visited[new_x][new_y]) and (grid[new_x][new_y] == 1):
								visited[new_x][new_y] = True
								next_level.append((new_x, new_y))
					count += len(next_level)
					queue = next_level
				max_count = max(max_count, count)
	return max_count
m = int(input())
n = int(input())
grid = []
for _ in range(m):
	grid.append([int(x) for x in input().split()])
print(solve(grid, m, n))


def cluster_size(array, mx, my, x, y):
	if x < 0 or x >= mx or y < 0 or (y >= my) or (array[x][y] == 0):
		return 0
	array[x][y] = 0
	return 1 + sum([cluster_size(array, mx, my, x + i, y + j) for i in (-1, 0, 1) for j in (-1, 0, 1) if i != 0 or j != 0])
mx = int(input())
my = int(input())
array = [[int(j) for j in input().split()] for i in range(mx)]
max_size = 0
for x in range(mx):
	for y in range(my):
		if array[x][y] == 1:
			max_size = max(max_size, cluster_size(array, mx, my, x, y))
print(max_size)


R = int(input())
C = int(input())

def dive(r, c):
	if G[r][c] == '0' or G[r][c] == 'X':
		return 0
	G[r][c] = 'X'
	return 1 + sum([dive(r + i, c + j) for i in range(-1, 2) for j in range(-1, 2)])
G = [['0'] * (C + 2)]
G += [['0'] + input().split() + ['0'] for _ in range(R)]
G += [['0'] * (C + 2)]
zones = []
for (r, row) in enumerate(G):
	for (c, val) in enumerate(row[:-1]):
		if val == '1' and G[r][c] != 'X':
			zones.append(dive(r, c))
print(max(zones))


visited = []
r = int(input())
c = int(input())
matrix = []
for i in range(0, r):
	matrix.append(input().split())

def getAdj(i, j):
	adj = []
	if i != 0:
		if matrix[i - 1][j] == '1':
			adj.append((i - 1, j))
		if j != c - 1 and matrix[i - 1][j + 1] == '1':
			adj.append((i - 1, j + 1))
		if j != 0 and matrix[i - 1][j - 1] == '1':
			adj.append((i - 1, j - 1))
	if i != r - 1:
		if matrix[i + 1][j] == '1':
			adj.append((i + 1, j))
		if j != c - 1 and matrix[i + 1][j + 1] == '1':
			adj.append((i + 1, j + 1))
		if j != 0 and matrix[i + 1][j - 1] == '1':
			adj.append((i + 1, j - 1))
	if j != 0 and matrix[i][j - 1] == '1':
		adj.append((i, j - 1))
	if j != c - 1 and matrix[i][j + 1] == '1':
		adj.append((i, j + 1))
	return adj

def dfs(index):
	stack = []
	stack.append(index)
	visitedTemp = []
	while len(stack) > 0:
		tempIndex = stack.pop()
		if tempIndex not in visited:
			visited.append(tempIndex)
			visitedTemp.append(tempIndex)
			adj = getAdj(tempIndex[0], tempIndex[1])
			for inx in adj:
				stack.append(inx)
	return len(visitedTemp)
maxV = 0
for i in range(0, r):
	for j in range(0, c):
		if matrix[i][j] == '1' and (i, j) not in visited:
			x = dfs((i, j))
			if x > maxV:
				maxV = x
print(maxV)


__author__ = 'Nathan'
m = int(input())
n = int(input())
array = []
for i in range(m):
	new_row = input().split()
	new_row = [int(x) for x in new_row]
	array.append(new_row)
unvisited_pos = {(x, y) for x in range(m) for y in range(n)}

def spread(array, current, unvisited_pos):
	size = 1
	to_do = [current]
	array[current[0]][current[1]] = 0
	while to_do:
		current = to_do.pop(0)
		if unvisited_pos.__contains__(current):
			unvisited_pos.remove(current)
		for delta in {(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)}:
			new_pos = tuple(map(sum, zip(delta, current)))
			if new_pos[0] > -1 and new_pos[0] < m and (new_pos[1] > -1) and (new_pos[1] < n) and unvisited_pos.__contains__(new_pos):
				if array[new_pos[0]][new_pos[1]] == 1:
					to_do.append((new_pos[0], new_pos[1]))
					array[new_pos[0]][new_pos[1]] = 0
					size += 1
	return size
largest = 0
while unvisited_pos:
	current = next(iter(unvisited_pos))
	if array[current[0]][current[1]]:
		group_size = spread(array, current, unvisited_pos)
		if group_size > largest:
			largest = group_size
	else:
		unvisited_pos.remove(current)
print(largest)


rows = int(input().strip())
cols = int(input().strip())

def find_parent(union_find, idx):
	while union_find[idx] != idx:
		idx = union_find[idx]
	return idx

def join(union_find, union_find_counts, idx1, idx2):
	idx1 = find_parent(union_find, idx1)
	idx2 = find_parent(union_find, idx2)
	union_find[idx2] = idx1
	union_find_counts[idx1] += union_find_counts[idx2]
	return idx1
uf = [0]
uf_cnts = [0]
prev_row = [0] * cols
for row in range(rows):
	this_row = [int(item) for item in input().strip().split()]
	for (idx, item) in enumerate(this_row):
		if not item:
			continue
		neighbors = set()
		neighbors.add(find_parent(uf, prev_row[max(idx - 1, 0)]))
		neighbors.add(find_parent(uf, prev_row[min(idx + 1, cols - 1)]))
		neighbors.add(find_parent(uf, prev_row[idx]))
		if idx > 0:
			neighbors.add(find_parent(uf, this_row[idx - 1]))
		neighbors.discard(0)
		this_row[idx] = None
		if not neighbors:
			this_row[idx] = len(uf)
			uf.append(len(uf))
			uf_cnts.append(1)
		while neighbors:
			region = neighbors.pop()
			if this_row[idx] is None:
				uf_cnts[region] += 1
				this_row[idx] = region
			else:
				this_row[idx] = join(uf, uf_cnts, this_row[idx], region)
	prev_row = this_row
print(max(uf_cnts))


def intput():
	return int(input())

def read_grid(m):
	grid = []
	for _ in range(m):
		grid.append([int(s) for s in input().split()])
	return grid

def add_if_valid(grid, queue, i, j, seen):
	if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] and ((i, j) not in seen):
		queue.append((i, j))
		seen.add((i, j))

def bfs(start, grid, seen):
	queue = [start]
	count = 0
	while len(queue) > 0:
		(i, j) = queue.pop(0)
		count += 1
		add_if_valid(grid, queue, i - 1, j, seen)
		add_if_valid(grid, queue, i, j - 1, seen)
		add_if_valid(grid, queue, i + 1, j, seen)
		add_if_valid(grid, queue, i, j + 1, seen)
		add_if_valid(grid, queue, i - 1, j - 1, seen)
		add_if_valid(grid, queue, i - 1, j + 1, seen)
		add_if_valid(grid, queue, i + 1, j - 1, seen)
		add_if_valid(grid, queue, i + 1, j + 1, seen)
	return count

def largest_region(grid, m, n):
	largest_region = 0
	seen = set()
	for i in range(m):
		for j in range(n):
			if grid[i][j] and (i, j) not in seen:
				seen.add((i, j))
				largest_region = max(largest_region, bfs((i, j), grid, seen))
	return largest_region
m = intput()
n = intput()
grid = read_grid(m)
print(largest_region(grid, m, n))


nrows = int(input())
ncols = int(input())
M = []
for i in range(nrows):
	r = [int(t) for t in input().split()]
	M.append(r)

def dfs(i, j):
	if i < 0 or j < 0:
		return 0
	if nrows <= i or ncols <= j:
		return 0
	m = M[i][j]
	if m == 0 or m == 4:
		return 0
	if m == 1:
		M[i][j] = 4
		s = 1
		s += dfs(i - 1, j)
		s += dfs(i - 1, j - 1)
		s += dfs(i, j - 1)
		s += dfs(i + 1, j - 1)
		s += dfs(i + 1, j)
		s += dfs(i + 1, j + 1)
		s += dfs(i, j + 1)
		s += dfs(i - 1, j + 1)
		return s

def do_region(i, j):
	s = dfs(i, j)
	for i in range(nrows):
		print(' '.join(map(str, M[i])))
	return s

def loop():
	(i, j) = (0, 0)
	MAX_REGION = 0
	while i < nrows:
		if M[i][j] == 1:
			s = dfs(i, j)
			if s > MAX_REGION:
				MAX_REGION = s
		j += 1
		if j == ncols:
			j = 0
			i += 1
	print(MAX_REGION)
loop()


def bfs(matrix, node, visited):
	size = 0
	toVisit = [node]
	visited.add(node)
	while len(toVisit) != 0:
		n = toVisit.pop(0)
		size += 1
		for kid in getKids(matrix, n, visited):
			toVisit.append(kid)
			visited.add(kid)
	return size

def getKids(matrix, node, visited):
	i = node[0]
	j = node[1]
	m = len(matrix)
	n = len(matrix[0])
	kids = []
	for x in range(i - 1, i + 2):
		for y in range(j - 1, j + 2):
			if x >= 0 and x < m and (y >= 0) and (y < n) and (matrix[x][y] == 1) and ((x, y) not in visited):
				kids.append((x, y))
	return kids

def solve():
	visited = set()
	res = 0
	m = int(input())
	n = int(input())
	matrix = [list(map(int, input().split(' '))) for i in range(m)]
	for i in range(m):
		for j in range(n):
			node = (i, j)
			if node not in visited:
				if matrix[i][j] > 0:
					res = max(res, bfs(matrix, node, visited))
				else:
					visited.add(node)
	return res
print(solve())


matrix = []

def componentSize(x, y, m, n):
	if x >= m or y >= n or x < 0 or (y < 0):
		return 0
	if matrix[x][y] == 0:
		return 0
	matrix[x][y] = 0
	return 1 + componentSize(x + 1, y, m, n) + componentSize(x - 1, y, m, n) + componentSize(x, y + 1, m, n) + componentSize(x, y - 1, m, n) + componentSize(x + 1, y + 1, m, n) + componentSize(x + 1, y - 1, m, n) + componentSize(x - 1, y - 1, m, n) + componentSize(x - 1, y + 1, m, n)
m = int(input())
n = int(input())
for x in range(0, m):
	row = [int(n) for n in input().split()]
	matrix.append(row)
maxSize = 0
numiter = 0
for x in range(0, m):
	for y in range(0, n):
		if matrix[x][y] == 1:
			s = componentSize(x, y, m, n)
			maxSize = max(maxSize, s)
			numiter += 1
print(maxSize)


def search(x, y, data):
	data[x][y] = '0'
	sum = 1
	if x - 1 >= 0 and data[x - 1][y] == '1':
		sum += search(x - 1, y, data)
	if y + 1 <= len(data[x]) - 1 and data[x][y + 1] == '1':
		sum += search(x, y + 1, data)
	if x + 1 <= len(data) - 1 and data[x + 1][y] == '1':
		sum += search(x + 1, y, data)
	if y - 1 >= 0 and data[x][y - 1] == '1':
		sum += search(x, y - 1, data)
	if y - 1 >= 0 and x - 1 >= 0 and (data[x - 1][y - 1] == '1'):
		sum += search(x - 1, y - 1, data)
	if y - 1 >= 0 and x + 1 <= len(data) - 1 and (data[x + 1][y - 1] == '1'):
		sum += search(x + 1, y - 1, data)
	if y + 1 <= len(data[x]) - 1 and x - 1 >= 0 and (data[x - 1][y + 1] == '1'):
		sum += search(x - 1, y + 1, data)
	if x + 1 <= len(data) - 1 and y + 1 <= len(data[x]) - 1 and (data[x + 1][y + 1] == '1'):
		sum += search(x + 1, y + 1, data)
	return sum
inX = int(input())
inY = int(input())
data = []
for x in range(inX):
	data.append(input().split())
biggest = 0
for x in range(inX):
	for y in range(inY):
		if data[x][y] == '1':
			found = search(x, y, data)
			if found > biggest:
				biggest = found
print(biggest)


f = '1'
nrow = int(input())
ncol = int(input())
plot = []
for row in range(nrow):
	plot.append(input().split())
visited = []

def near(row, col):
	return [(x, y) for x in range(max(0, row - 1), min(nrow, row + 2)) for y in range(max(0, col - 1), min(ncol, col + 2)) if (x, y) != (row, col)]

def got(row, col):
	return ((row, col) not in visited) & (plot[row][col] == f)
mreg = 0
for row in range(nrow):
	for col in range(ncol):
		if got(row, col):
			visited.append((row, col))
			reg = 1
			tneighbors = {(x, y) for (x, y) in near(row, col) if got(x, y)}
			while tneighbors != set():
				visiting = tneighbors.pop()
				visited.append(visiting)
				reg = reg + 1
				mreg = max(reg, mreg)
				tneighbors = tneighbors.union(set([x for x in near(visiting[0], visiting[1]) if got(x[0], x[1])]))
			mreg = max(reg, mreg)
print(mreg)


m = int(input())
n = int(input())
mat = []
for _ in range(m):
	mat.append([int(x == '1') for x in input().strip().split(' ')])
ones = set()
for row in range(m):
	for col in range(n):
		if mat[row][col]:
			ones.add((row, col))
regions = []
while ones:
	n = ones.pop()
	region = [n]
	regions.append(region)
	unchecked = [n]
	while unchecked:
		(xr, xc) = unchecked.pop()
		for r in [-1, 0, 1]:
			for c in [-1, 0, 1]:
				p = (xr + r, xc + c)
				if p in ones:
					ones.remove(p)
					region.append(p)
					unchecked.append(p)
print(max((len(region) for region in regions), default=0))


import fileinput
inputs = []
for line in fileinput.input():
	inputs.append([int(i) for i in line.strip().split()])
(m, n, matrix) = (inputs[0][0], inputs[1][0], inputs[2:])
(graph, graphcopy) = ({}, {})

def dfs(graph, start):
	(visited, stack) = (set(), [start])
	while stack:
		vertex = stack.pop()
		if vertex not in visited:
			visited.add(vertex)
			stack.extend(graph[vertex] - visited)
	return visited
for row in range(m):
	for col in range(n):
		graph[str(row) + str(col)] = set([])
for row in range(m):
	for col in range(n):
		if matrix[row][col] == 1:
			if row > 0 and col > 0:
				if matrix[row - 1][col - 1] == 1:
					graph[str(row) + str(col)].add(str(row - 1) + str(col - 1))
			if row > 0:
				if matrix[row - 1][col] == 1:
					graph[str(row) + str(col)].add(str(row - 1) + str(col))
			if row > 0 and col < n - 1:
				if matrix[row - 1][col + 1] == 1:
					graph[str(row) + str(col)].add(str(row - 1) + str(col + 1))
			if col < n - 1:
				if matrix[row][col + 1] == 1:
					graph[str(row) + str(col)].add(str(row) + str(col + 1))
			if row < m - 1 and col < n - 1:
				if matrix[row + 1][col + 1] == 1:
					graph[str(row) + str(col)].add(str(row + 1) + str(col + 1))
			if row < m - 1:
				if matrix[row + 1][col] == 1:
					graph[str(row) + str(col)].add(str(row + 1) + str(col))
			if row < m - 1 and col > 0:
				if matrix[row + 1][col - 1] == 1:
					graph[str(row) + str(col)].add(str(row + 1) + str(col - 1))
			if col > 0:
				if matrix[row][col - 1] == 1:
					graph[str(row) + str(col)].add(str(row) + str(col - 1))
for key in graph:
	if graph[key] != set([]):
		graphcopy[key] = graph[key]
(res, graph) = ([], graphcopy.copy())
for cell in graph:
	region = dfs(graphcopy, cell)
	res += [len(region)]
	graphcopy = graph.copy()
res = max(res) if res else 1
print(res)


class Board(object):

	def __init__(self, num_rows, num_cols, arr):
		self.movs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
		self.rows = num_rows
		self.columns = num_columns
		self.arr = arr
		self.visited = [[False for _ in range(num_columns)] for _ in range(num_rows)]
		self.current_path = 0
		self.max_path = -1

	def dfs(self, pos):
		if self.visited[pos[0]][pos[1]]:
			return None
		self.visited[pos[0]][pos[1]] = True
		self.current_path += 1
		(tmp_row, tmp_column) = (0, 0)
		for mov in self.movs:
			tmp_row = mov[0] + pos[0]
			tmp_column = mov[1] + pos[1]
			if tmp_row < 0 or tmp_row >= self.rows:
				continue
			if tmp_column < 0 or tmp_column >= self.columns:
				continue
			if self.arr[tmp_row][tmp_column] == 1:
				self.dfs((tmp_row, tmp_column))

	def check_paths(self):
		self.max_path = max(self.current_path, self.max_path)
		self.current_path = 0

	def solve(self):
		for row in range(self.rows):
			for column in range(self.columns):
				if self.arr[row][column] == 1 and (not self.visited[row][column]):
					self.dfs((row, column))
					self.check_paths()
				self.visited[row][column] = True
		return self.max_path
num_rows = int(input())
num_columns = int(input())
arr = [list(map(int, input().split())) for _ in range(num_rows)]
print(Board(num_rows, num_columns, arr).solve())


from collections import deque
m = int(input())
n = int(input())
grid = list()
for i in range(m):
	grid.append(list(map(int, input().split())))
visited = list((list((False for i in range(n))) for j in range(m)))
largest = 0
for i in range(m):
	for j in range(n):
		if visited[i][j]:
			continue
		if grid[i][j] == 1:
			q = deque([(i, j)])
			regionsize = 0
			while q:
				(r, c) = q.pop()
				if visited[r][c]:
					continue
				visited[r][c] = True
				if grid[r][c] == 1:
					regionsize += 1
					for dr in range(-1, 2):
						for dc in range(-1, 2):
							nr = r + dr
							nc = c + dc
							if nr >= 0 and nr < m and (nc >= 0) and (nc < n):
								q.appendleft((nr, nc))
			if regionsize > largest:
				largest = regionsize
print(largest)


import itertools

def strongly_connected_components_path(vertices, edges):
	identified = set()
	stack = []
	index = {}
	boundaries = []

	def dfs(v):
		index[v] = len(stack)
		stack.append(v)
		boundaries.append(index[v])
		for w in edges[v]:
			if w not in index:
				for scc in dfs(w):
					yield scc
			elif w not in identified:
				while index[w] < boundaries[-1]:
					boundaries.pop()
		if boundaries[-1] == index[v]:
			boundaries.pop()
			scc = set(stack[index[v]:])
			del stack[index[v]:]
			identified.update(scc)
			yield scc
	for v in vertices:
		if v not in index:
			for scc in dfs(v):
				yield scc
m = input('')
m = int(m)
n = input('')
n = int(n)
grid = []
for i in range(m):
	x = input('')
	grid.append(list(map(lambda y: int(y), x.split(' '))))
vert = list(itertools.product(set(range(m)), set(range(n))))
edges1 = {}
for u in range(m):
	for v1 in range(n):
		edges1[u, v1] = []
for u in range(m):
	for v1 in range(n):
		for a in [-1, 0, 1]:
			for b in [-1, 0, 1]:
				if grid[u][v1] == 0 or (a == 0 and b == 0) or u + a < 0 or (u + a >= m) or (v1 + b < 0) or (v1 + b >= n):
					continue
				if grid[u + a][v1 + b] == 1:
					edges1[u, v1].append((u + a, v1 + b))
m = -1
for scc in strongly_connected_components_path(vert, edges1):
	m = max(m, len(scc))
print(m)


m = int(input())
n = int(input())
row = []
arr = []
for i in range(m):
	row = list(map(int, input().split()))
	arr.append(row)
lens = []
for i in range(0, m):
	counter = 1
	if arr[i].count(1) > 0:
		si = i
		sj = arr[i].index(1)
	queue = []
	queue.append([si, sj])
	arr[si][sj] = 0
	while len(queue) >= 0:
		for adj in ([0, -1], [0, 1], [1, 0], [-1, 0], [1, -1], [1, 1], [-1, -1], [-1, 1]):
			ni = si + adj[0]
			nj = sj + adj[1]
			if 0 <= ni < m and 0 <= nj < n and (arr[ni][nj] == 1):
				queue.append([ni, nj])
				counter += 1
				arr[ni][nj] = 0
		try:
			t = queue.pop(0)
			si = t[0]
			sj = t[1]
		except IndexError:
			break
	lens.append(counter)
print(max(lens))


def findNext():
	for i in range(0, m):
		for j in range(0, n):
			if mapGrid[i][j] == 1:
				return (i, j)
	return None

def connectCell(r, c):
	if r < 0 or r >= m or c < 0 or (c >= n):
		return 0
	if mapGrid[r][c] != 1:
		return 0
	ans = 1
	mapGrid[r][c] = 'X'
	for i in range(0, 8):
		ans += connectCell(r + dr[i], c + dc[i])
	return ans
m = int(input())
n = int(input())
mapGrid = []
for i in range(0, m):
	row = list(map(int, input().strip().split(' ')))
	mapGrid.append(row)
dr = [1, 1, 0, -1, -1, -1, 0, 1]
dc = [0, 1, 1, 1, 0, -1, -1, -1]
nextCoord = findNext()
maxSoFar = 0
while nextCoord != None:
	(x, y) = nextCoord
	localMax = connectCell(x, y)
	if maxSoFar < localMax:
		maxSoFar = localMax
	nextCoord = findNext()
print(maxSoFar)


row = int(input())
input()
grid = [[int(x) for x in input().split()] for j in range(row)]
possible = {(j, i) for i in range(len(grid[0])) for j in range(row) if grid[j][i]}

def neighbour(grid, i, j):
	possible_moves = [(1, 0), (0, 1), (1, 1), (-1, 0), (0, -1), (-1, -1), (-1, 1), (1, -1)]
	(width, height) = (len(grid[0]), len(grid))
	for (x, y) in possible_moves:
		if 0 <= i + x < height and 0 <= y + j < width and grid[x + i][y + j]:
			yield (i + x, y + j)
max_c = 0
while possible:
	queue = [possible.pop()]
	done = set([queue[0]])
	count = 1
	while queue:
		point = queue.pop(0)
		for (x, y) in neighbour(grid, point[0], point[1]):
			if grid[x][y] and (x, y) in possible and ((x, y) not in done):
				queue.append((x, y))
				done.add((x, y))
				count += 1
	if max_c < count:
		max_c = count
	possible.difference_update(done)
print(max_c)


from operator import add
conns = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]

def zero(seen):
	for s in seen:
		mat[s[0]][s[1]] = 0

def crawl():
	seen = []
	neighbors = [[i, j]]
	cnt = 0
	while neighbors:
		x = neighbors[0]
		seen.append(x)
		neighbors.remove(x)
		cnt += 1
		for mod in conns:
			c = list(map(add, x, mod))
			if 0 <= c[0] < m and 0 <= c[1] < n and (mat[c[0]][c[1]] == 1) and (c not in neighbors) and (c not in seen):
				neighbors.append(c)
	zero(seen)
	return cnt
m = int(input())
mr = range(m)
n = int(input())
nr = range(n)
mat = [[0 for i in nr] for j in mr]
for i in mr:
	r = list(map(int, input().split()))
	for j in nr:
		mat[i][j] = r[j]
count = 0
for i in mr:
	for j in nr:
		if mat[i][j] == 1:
			cc = crawl()
			if cc > count:
				count = cc
print(count)