<|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 hash maps (or 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 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 DFS 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 DFS, where E ≤ 2K, so it runs comfortably for K up to 2·10^5.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

// Maximum number of initial black cells
static const int MAXK = 200000;

int K;
int xcoord[MAXK], ycoord[MAXK];
vector<int> adj[MAXK];
bool visited[MAXK];

// Maps to remember the last point seen in each row/column
unordered_map<int,int> row_last, col_last;

// Read input and build adjacency list linking points in same row or column
void read_input() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> K;
    for(int i = 0; i < K; i++) {
        cin >> xcoord[i] >> ycoord[i];

        // Link with the previous point in the same row, if any
        auto rit = row_last.find(xcoord[i]);
        if (rit != row_last.end()) {
            int j = rit->second;
            adj[i].push_back(j);
            adj[j].push_back(i);
        } else {
            row_last[xcoord[i]] = i;
        }

        // Link with the previous point in the same column, if any
        auto cit = col_last.find(ycoord[i]);
        if (cit != col_last.end()) {
            int j = cit->second;
            adj[i].push_back(j);
            adj[j].push_back(i);
        } else {
            col_last[ycoord[i]] = i;
        }
    }
}

// DFS to explore a component; collects its distinct rows and columns
void dfs(int u, unordered_set<int>& rows, unordered_set<int>& cols) {
    visited[u] = true;
    rows.insert(xcoord[u]);
    cols.insert(ycoord[u]);
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, rows, cols);
        }
    }
}

int main() {
    read_input();

    long long answer = 0;
    // Explore each component
    for (int i = 0; i < K; i++) {
        if (!visited[i]) {
            unordered_set<int> rows, cols;
            dfs(i, rows, cols);
            // This component fills all R × C positions
            answer += (long long)rows.size() * cols.size();
        }
    }

    cout << answer << "\n";
    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()
```