class Solution {
  public:
    vector<int> idx, sz;
    int root(int x) {
        while(idx[x] != x) {
            idx[x] = idx[idx[x]];
            x = idx[x];
        }
        return x;
    }
    void join(int x, int y) {
        int root_x = root(x), root_y = root(y);
        if(root_x != root_y) {
            if(sz[root_x] < sz[root_y]) {
                idx[root_x] = idx[root_y];
                sz[root_y] += sz[root_x];
            }
            else {
                idx[root_y] = idx[root_x];
                sz[root_x] += sz[root_y];
            }
        }
    }

    vector<int> numOfIslands(int n, int m, vector<vector<int>> &operators) {
        // code here
        idx.resize(n * m);
        sz.resize(n * m);
        map<pair<int, int>, int> g;
        int c = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                g[make_pair(i, j)] = c++;
            }
        }
        for(int i = 0; i < n * m; i++) {
            idx[i] = i;
            sz[i] = 1;
        }
        vector<vector<int>> mat(n, vector<int>(m, 0));
        vector<int> res;
        set<int> st;
        for(int i = 0; i < operators.size(); i++) {
            int ci = operators[i][0], cj = operators[i][1];
            mat[ci][cj] = 1;
            if(ci + 1 < n and mat[ci + 1][cj] == 1) {
                if(st.find(root(g[make_pair(ci + 1, cj)])) != st.end()) {
                    st.erase(st.find(root(g[make_pair(ci + 1, cj)])));
                }
                join(root(g[make_pair(ci, cj)]), root(g[make_pair(ci + 1, cj)]));
//                cout << "DA" << endl;
            }
            if(ci - 1 >= 0 and mat[ci - 1][cj] == 1) {
                if(st.find(root(g[make_pair(ci - 1, cj)])) != st.end()) {
                    st.erase(st.find(root(g[make_pair(ci - 1, cj)])));
                }
                join(root(g[make_pair(ci, cj)]), root(g[make_pair(ci - 1, cj)]));
//                cout << "DA" << endl;
            }
            if(cj + 1 < m and mat[ci][cj + 1] == 1){
                if(st.find(root(g[make_pair(ci, cj + 1)])) != st.end()) {
                    st.erase(st.find(root(g[make_pair(ci, cj + 1)])));
                }
                join(root(g[make_pair(ci, cj)]), root(g[make_pair(ci, cj + 1)]));
            }
            if(cj - 1 >= 0 and mat[ci][cj - 1] == 1) {
                if(st.find(root(g[make_pair(ci, cj - 1)])) != st.end()) {
                    st.erase(st.find(root(g[make_pair(ci, cj - 1)])));
                }
                join(root(g[make_pair(ci, cj)]), root(g[make_pair(ci, cj - 1)]));
//                cout << "DA" << endl;
            }
//            cout << ci << " " << cj << " " << idx[g[make_pair(ci, cj)]] << endl;
            st.insert(root(g[make_pair(ci, cj)]));
            res.push_back((int) st.size());
        }
        return res;
    }
};