<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

369. Game
Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Vasya loves his new game which is played on an infinite rectangular grid where K cells are initially black, all other cells are white. The move of the game is to find three black cells which are vertices of some rectangle with sides parallel to coordinate axis such that the fourth vertex of the rectangle is white. In this case you need to paint the fourth vertex black. Vasya asks you to write a program which calculates the number of black cells in the end of the game, i.e. when no more moves can be made.

Input
The first line contains an integer K (0 ≤ K≤ 2· 105). The next K lines contain two integers each — coordinates of black cells Xi and Yi (-109 ≤ Xi, Yi ≤ 109).

Output
Output the answer to the task.

Example(s)
sample input
sample output
3
1 1
1 2
2 2
4

sample input
sample output
5
0 0
1 0
0 1
1 2
2 1
9

<|response|>
1. Abridged Problem Statement
You are given K black cells on an infinite 2D grid (all other cells are white). Repeatedly, whenever three corners of an axis-aligned rectangle are black and the fourth corner is white, you paint that fourth corner black. When no more moves are possible, how many cells are black?

2. Key Observations
- Any time you can fill one missing corner of a rectangle, that operation “connects” the row and column of that corner to the existing black structure.
- Ultimately, in each connected group of black cells (where connectivity is via shared row or shared column), every combination of the involved rows and columns becomes black.
- Thus, if a component involves R distinct x-coordinates (rows) and C distinct y-coordinates (columns), it will end up with R·C black cells.

3. Full Solution Approach
a. Read the K input points, store their x[i], y[i].
b. Build an undirected graph on these points:
   - Maintain two ordered maps row_last and col_last.
   - When reading a point i with x[i], if row_last[x[i]] exists as some index j, link i–j. Otherwise set row_last[x[i]] = i.
   - Do the same with col_last[y[i]].
   This ensures all points that share a row or column are in one connected component.
c. Run a flood fill (iterative DFS, or BFS) over these K nodes. For each component:
   - Track a set of distinct x-coordinates and a set of distinct y-coordinates.
   - When the traversal finishes that component, add (number of distinct x’s) × (number of distinct y’s) to the answer.
d. Output the accumulated sum.

Time complexity is O(K log K) for map operations plus O(K + E) for the traversal, where E ≤ 2K, so it runs comfortably for K up to 2·10^5.

4. C++ Implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int> x, y;
vector<vector<int>> adj;

void read() {
    cin >> n;
    x.resize(n);
    y.resize(n);
    adj.assign(n, {});

    map<int, int> col_last, row_last;
    for(int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];

        if(col_last.count(y[i])) {
            adj[i].push_back(col_last[y[i]]);
            adj[col_last[y[i]]].push_back(i);
        } else {
            col_last[y[i]] = i;
        }

        if(row_last.count(x[i])) {
            adj[i].push_back(row_last[x[i]]);
            adj[row_last[x[i]]].push_back(i);
        } else {
            row_last[x[i]] = i;
        }
    }
}

void solve() {
    // Each black cell links the previous cell sharing its row and the previous
    // cell sharing its column, building a graph whose connected components are
    // closed under the rectangle-completion move. Within one component every
    // (row, column) pair that appears can eventually be filled, so the final
    // count of black cells in that component is exactly the number of distinct
    // rows times the number of distinct columns it touches.
    //
    // Flood fill each component, collect its distinct row and column
    // coordinates in sets, and accumulate rows * cols across all components.

    vector<char> used(n, 0);
    int64_t answer = 0;

    for(int s = 0; s < n; s++) {
        if(used[s]) {
            continue;
        }

        set<int> rw, cl;
        vector<int> stack = {s};
        used[s] = 1;
        while(!stack.empty()) {
            int u = stack.back();
            stack.pop_back();
            rw.insert(x[u]);
            cl.insert(y[u]);
            for(int v: adj[u]) {
                if(!used[v]) {
                    used[v] = 1;
                    stack.push_back(v);
                }
            }
        }

        answer += (int64_t)rw.size() * (int64_t)cl.size();
    }

    cout << answer << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments
```python
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    K = int(input())
    xs = [0]*K
    ys = [0]*K

    # Map each row x -> list of point indices
    # and each column y -> list of point indices
    rows_map = {}
    cols_map = {}

    for i in range(K):
        xi, yi = map(int, input().split())
        xs[i], ys[i] = xi, yi
        rows_map.setdefault(xi, []).append(i)
        cols_map.setdefault(yi, []).append(i)

    visited = [False]*K
    answer = 0

    # We will BFS for each unvisited point
    for i in range(K):
        if not visited[i]:
            queue = deque([i])
            visited[i] = True
            comp_rows = set()
            comp_cols = set()

            while queue:
                u = queue.popleft()
                rx, ry = xs[u], ys[u]
                comp_rows.add(rx)
                comp_cols.add(ry)

                # Enqueue all others in the same row
                for v in rows_map.get(rx, []):
                    if not visited[v]:
                        visited[v] = True
                        queue.append(v)
                # Clear so we don't revisit this row
                rows_map[rx] = []

                # Enqueue all others in the same column
                for v in cols_map.get(ry, []):
                    if not visited[v]:
                        visited[v] = True
                        queue.append(v)
                # Clear so we don't revisit this column
                cols_map[ry] = []

            # All combinations of these rows and cols become black
            answer += len(comp_rows) * len(comp_cols)

    print(answer)

if __name__ == "__main__":
    sys.setrecursionlimit(10**7)
    main()
```
