class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b

class UnionFind:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.count = n

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

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.father[root_a] = root_b
            self.count -= 1


class Solution:
    """
    @param n: An integer
    @param m: An integer
    @param operators: an array of point
    @return: an integer array
    """

    def numIslands2(self, n, m, operators):
        # write your code here
        if n == 0 or m == 0 or not operators:
            return []
        uf = UnionFind(m * n)
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        waters = m * n
        grid = [[0] * m for _ in range(n)]
        res = []
        for oper in operators:
            i = oper.x
            j = oper.y

            # must have the below area, otherwise failed for case: [[0,0],[0,1],[2,2],[2,2]]
            # 有相同的岛屿
            if grid[i][j] == 1:
                res.append(cnt)
                continue

            grid[i][j] = 1
            waters -= 1
            for k in range(4):
                x = i + dirs[k][0]
                y = j + dirs[k][1]
                if x < 0 or x >= n or y < 0 or y >= m:
                    continue
                if grid[x][y] == 1:
                    uf.union(i * m + j, x * m + y)
            cnt = uf.count - waters
            res.append(cnt)

        return res