#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int maxn = 20005;

class Solution {
  public:
    vector<int> idx, sz;
    int root(int x) {
        while(x != idx[x]) {
            idx[x] = idx[idx[x]];
            x = idx[x];
        }
        return x;
    }
    void join(int x, int y) {
        int root_x = root(x);
        int root_y = root(y);
        if(root_x != root_y) {
            if(sz[root_x] > sz[root_y]) {
                idx[root_y] = idx[root_x];
                sz[root_x] += sz[root_y];
            }
            else {
                idx[root_x] = idx[root_y];
                sz[root_y] += sz[root_x];
            }
        }
    }
    vector<int> numOfIslands(int n, int m, vector<vector<int>> &operators) {
        idx.resize(n * m);
        sz.resize(n * m);
        for(int i = 0; i < n * m; i++) {
            idx[i] = i;
            sz[i] = 1;
        }
        map<pair<int, int>, int> g;
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                g[make_pair(i, j)] = cnt;
                cnt++;
            }
        }
        int di[] = {-1, 1, 0, 0};
        int dj[] = {0, 0, -1, 1};
        set<int> st;
        vector<int> res;
        vector<vector<int>> mat(n, vector<int>(m, 0));
        for(int i= 0; i < operators.size(); i++) {
            int ci = operators[i][0], cj = operators[i][1];
            mat[ci][cj] = 1;
            for(int k = 0; k < 4; k++) {
                int ti = di[k] + ci;
                int tj = dj[k] + cj;

                if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] == 1) {
                    if(st.find(root(g[make_pair(ti, tj)])) != st.end()) {
                        st.erase(st.find(root(g[make_pair(ti, tj)])));
                    }
                    int root_1 = root(g[make_pair(ci, cj)]), root_2 = root(g[make_pair(ti, tj)]);
                    join(root_1, root_2);
                }
            }
            st.insert(root(g[make_pair(ci, cj)]));
            res.push_back(st.size());
        }

        return res;
    }
};

int main() {

    return 0;
}