1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
        return (ll(p.first) << 32) | p.second;
    }
};

unordered_map<int, unordered_set<int>> row_map, col_map;
unordered_set<pair<int, int>, PairHash> current_blocks;
unordered_map<int, int> row_degree, col_degree;
unordered_map<int, bool> active_row, active_col;
ll core_size = 0;
queue<pair<bool, int>> processing_queue;

void process_queue() {
    while (!processing_queue.empty()) {
        auto entry = processing_queue.front();
        processing_queue.pop();
        bool is_col = entry.first;
        int idx = entry.second;

        if (is_col) {
            if (!active_col[idx]) continue;
            active_col[idx] = false;

            for (int x : col_map[idx]) {
                if (current_blocks.count({x, idx}) && active_row[x]) {
                    core_size--;
                }
                row_map[x].erase(idx);
                row_degree[x]--;
                if (active_row[x] && row_degree[x] < 2) {
                    processing_queue.push({false, x});
                }
            }
            col_map[idx].clear();
            col_degree[idx] = 0;
        } else {
            if (!active_row[idx]) continue;
            active_row[idx] = false;

            for (int y : row_map[idx]) {
                if (current_blocks.count({idx, y}) && active_col[y]) {
                    core_size--;
                }
                col_map[y].erase(idx);
                col_degree[y]--;
                if (active_col[y] && col_degree[y] < 2) {
                    processing_queue.push({true, y});
                }
            }
            row_map[idx].clear();
            row_degree[idx] = 0;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k, q;
    cin >> n >> m >> k >> q;

    current_blocks.reserve(k + q);
    row_map.reserve(n + 1);
    col_map.reserve(m + 1);

    for (int i = 0; i < k; ++i) {
        int x, y;
        cin >> x >> y;
        current_blocks.insert({x, y});
        row_map[x].insert(y);
        col_map[y].insert(x);
        row_degree[x]++;
        col_degree[y]++;
    }

    for (auto& p : row_degree) active_row[p.first] = true;
    for (auto& p : col_degree) active_col[p.first] = true;

    core_size = current_blocks.size();

    for (auto& p : row_degree) {
        if (p.second < 2) processing_queue.push({false, p.first});
    }
    for (auto& p : col_degree) {
        if (p.second < 2) processing_queue.push({true, p.first});
    }

    process_queue();
    cout << current_blocks.size() - core_size << '\n';

    for (int i = 0; i < q; ++i) {
        int x, y;
        cin >> x >> y;
        pair<int, int> block = {x, y};

        if (current_blocks.count(block)) {
            current_blocks.erase(block);
            row_map[x].erase(y);
            col_map[y].erase(x);
            bool was_in_core = active_row[x] && active_col[y];
            row_degree[x]--;
            col_degree[y]--;

            if (was_in_core) core_size--;

            if (active_row[x] && row_degree[x] < 2) processing_queue.push({false, x});
            if (active_col[y] && col_degree[y] < 2) processing_queue.push({true, y});
        } else {
            current_blocks.insert(block);
            row_map[x].insert(y);
            col_map[y].insert(x);
            bool is_in_core = active_row[x] && active_col[y];
            row_degree[x]++;
            col_degree[y]++;

            if (is_in_core) core_size++;
        }

        process_queue();
        cout << current_blocks.size() - core_size << '\n';
    }

    return 0;
}