class UnionFind:
  def __init__(self, h, w):
    self.parent = {}
    self.size = {}

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

  def union(self, x, y):
    rootX = self.find(x)
    rootY = self.find(y)

    if rootX != rootY:
      if self.size[rootX] < self.size[rootY]:
        rootX, rootY = rootY, rootX
      self.parent[rootY] = rootX
      self.size[rootX] += self.size[rootY]

  def add(self, x):
    if x not in self.parent:
      self.parent[x] = x
      self.size[x] = 1

def dfs_fill(grid, h, w, union_find, row, col, visited):
  directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
  stack = [(row, col)]

  while stack:
    r, c = stack.pop()
    if visited[r][c]:
      continue

    visited[r][c] = True

    union_find.add((r, c)) # add cell to union

    for dr, dc in directions:
      new_row, new_col = r + dr, c + dc
      if 0 <= new_row < h and 0 <= new_col < w and grid[new_row][new_col] == 1 and not visited[new_row][new_col]:
        union_find.add((new_row, new_col))
        union_find.union((r, c), (new_row, new_col))
        stack.append((new_row, new_col))

def biggest_connected_component(h, w, grid):
  union_find = UnionFind(h, w)
  visited = [[False] * w for _ in range(h)]

  for i in range(h):
    for j in range(w):
      if grid[i][j] == 1 and not visited[i][j]:
        dfs_fill(grid, h, w, union_find, i, j, visited)

  max_component = max(union_find.size.values(), default = 0) # extract initial largest connected component

  for i in range(h):
    # filled_cells = set()
    for j in range(w):
      # filled_cells.add((i, j))
      union_find.add((i, j))

    for j in range(1, w):
      if 0 <= i < h and 0 <= j - 1 < w and grid[i][j - 1] == 1:
        union_find.union((i, j - 1), (i, j))
      if 0 <= i - 1 < h and 0 <= j < w and grid[i - 1][j] == 1:
        union_find.union((i - 1, j), (i, j))
      if 0 <= i < h and 0 <= j + 1 < w and grid[i][j + 1] == 1:
        union_find.union((i, j + 1), (i, j))
      if 0 <= i + 1< h and 0 <= j < w and grid[i + 1][j] == 1:
        union_find.union((i + 1, j), (i, j))

    max_component = max(max_component, max(union_find.size.values()))

  for j in range(w):
    # filled_cells = set()
    for i in range(h):
      # filled_cells.add((i, j))
      union_find.add((i, j))

    for i in range(1, h):
      if 0 <= i < h and 0 <= j - 1 < w and grid[i][j - 1] == 1:
        union_find.union((i, j - 1), (i, j))
      if 0 <= i - 1 < h and 0 <= j < w and grid[i - 1][j] == 1:
        union_find.union((i - 1, j), (i, j))
      if 0 <= i < h and 0 <= j + 1 < w and grid[i][j + 1] == 1:
        union_find.union((i, j + 1), (i, j))
      if 0 <= i + 1< h and 0 <= j < w and grid[i + 1][j] == 1:
        union_find.union((i + 1, j), (i, j))

    max_component = max(max_component, max(union_find.size.values()))

  return max_component



# driver code (not part of OA)
h, w = 3, 5
grid = [
    [1, 0, 1, 0, 0],
    [0, 1, 0, 0, 0],
    [1, 0, 1, 0, 0],
]
print(biggest_connected_component(h, w, grid))
print(grid)