class DisjointSet{
private:
    int numberOfSets;
    vector<int> parent,size;
    
    void initializeParentAndSizeDataStructures()
    {
        parent.clear();
        size.clear();
        parent.resize(numberOfSets);
        size.resize(numberOfSets);
        for(int setIdx = 0; setIdx < numberOfSets; setIdx += 1)
        {
            parent[setIdx] = setIdx;
            size[setIdx] = 1;
        }
    }
public:
    
    DisjointSet(int numberOfSets)
    {
        this->numberOfSets = numberOfSets;
        initializeParentAndSizeDataStructures();
    }
    
    int getParent(int element)
    {
        if(element == parent[element])
        {
            return element;
        }
        return parent[element] = getParent(parent[element]);
    }

    int getSize(int element)
    {
        return size[getParent(element)];
    }

    void connectElements(int element1,int element2)
    {
        element1 = getParent(element1);
        element2 = getParent(element2);
        if(element1 == element2)
            return;
        if(size[element1] < size[element2])
            swap(element1,element2);
        parent[element2] = element1;
        size[element1] += size[element2];
    }
};

class Solution {
private:

    enum brickStatus{
        NotPresent = 0, 
        Present = 1,
        Removed = -1  
    };

    int numberOfRows,numberOfCols;
    vector<vector<int>> grid,hits;
    
    int getId(int rowIdx,int colIdx)
    {
        return rowIdx * numberOfCols + colIdx + 1;
    }
    
    bool isBrickPresent(int rowIdx,int colIdx)
    {
        return grid[rowIdx][colIdx] == Present;
    }
    
    bool isARemovedBrick(int rowIdx,int colIdx)
    {
        return grid[rowIdx][colIdx] == Removed;
    }

    void removeBrick(int rowIdx,int colIdx)
    {
        grid[rowIdx][colIdx] = Removed;
    }
    
    void addBrick(int rowIdx,int colIdx)
    {
        grid[rowIdx][colIdx] = Present;
    }
    
    void removeAllBricksPresentInHitsArray()
    {
        for(vector<int> brick : hits)
        {
            int rowIdx = brick[0];
            int colIdx = brick[1];
            if(isBrickPresent(rowIdx,colIdx))
            {
                removeBrick(rowIdx,colIdx);
            }  
        }
    }
    
    bool isValid(int rowIdx,int colIdx)
    {
        return rowIdx >= 0 and rowIdx < numberOfRows and colIdx >= 0 and colIdx < numberOfCols and isBrickPresent(rowIdx,colIdx);
    }

    void connectBrickToNeighbours(int rowIdx,int colIdx,DisjointSet &disjointSet)
    {
        int currentCellId = getId(rowIdx,colIdx);
        int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 
        
        for(int dir = 0; dir < 4; dir++)
        {
            int nextRowIdx = rowIdx + directions[dir][0];
            int nextColIdx = colIdx + directions[dir][1];
            if(isValid(nextRowIdx,nextColIdx))
            {
                int nextCellId = getId(nextRowIdx,nextColIdx);
                disjointSet.connectElements(currentCellId,nextCellId);
            }
        }
        if(rowIdx == 0)
        {
            disjointSet.connectElements(0,currentCellId);
        }
    }

    void connectAllBricks(DisjointSet &disjointSet)
    {
        for(int rowIdx = 0; rowIdx < numberOfRows; rowIdx++)
        {
            for(int colIdx = 0; colIdx < numberOfCols; colIdx++)
            {
                if(isBrickPresent(rowIdx,colIdx))
                {
                    connectBrickToNeighbours(rowIdx,colIdx,disjointSet);
                }
            }
        }   
    }
    
    vector<int> getHitBricksByAddingAllRemovedBricks(DisjointSet &disjointSet)
    {
        int numberOfBricksConnectedToRoof = disjointSet.getSize(0);
        vector<int> hitBricks(hits.size());
        for(int hit = hits.size() - 1; hit >= 0; hit--)
        {
            int rowIdx = hits[hit][0];
            int colIdx = hits[hit][1];
            if(isARemovedBrick(rowIdx,colIdx))
            {
                addBrick(rowIdx,colIdx);
                connectBrickToNeighbours(rowIdx,colIdx,disjointSet);
                int numberOfBricksConnectedToRoofAfterAddingBackTheBrick = disjointSet.getSize(0);
                hitBricks[hit] = max(numberOfBricksConnectedToRoofAfterAddingBackTheBrick - numberOfBricksConnectedToRoof - 1,0);
                numberOfBricksConnectedToRoof = numberOfBricksConnectedToRoofAfterAddingBackTheBrick;
            }
        }
        return hitBricks;
    }
    
    vector<int> getHitBricks()
    {
        // initialize Disjoint Set with number of sets = numberOfCols * numberOfRows
        DisjointSet disjointSet(numberOfRows * numberOfCols + 1);
        
        // First Remove all the bricks that are present in hits array.
        removeAllBricksPresentInHitsArray();
        
        // Connect all the bricks that are present.
        connectAllBricks(disjointSet);
        
        // Add all the removed bricks back
        return getHitBricksByAddingAllRemovedBricks(disjointSet);
    }
    
public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        this->numberOfRows = grid.size();
        this->numberOfCols = grid[0].size();
        this->grid = grid;
        this->hits = hits;
        return getHitBricks();
    }
};