P3913 Rooks' Attack

On an $N \times N$ chessboard, there are $K$ rooks. The $i$-th rook is located at row $R_i$ and column $C_i$. Find the number of cells attacked by at least one rook. A rook can attack all cells in the same row or the same column.

The first line contains 2 integers $N, K$. The next $K$ lines each contain 2 integers $R_i, C_i$.

Output one integer, the number of cells that are attacked.

• For 30% of the testdata, $1 \le N \le 10^3; 1 \le K \le 10^3$. • For 60% of the testdata, $1 \le N \le 10^6; 1 \le K \le 10^6$. • For 100% of the testdata, $1 \le N \le 10^9; 1 \le K \le 10^6; 1 \le R_i, C_i \le N$. Translated by ChatGPT 5