Description

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.

Input Format

The first line contains 2 integers $N, K$.

The next $K$ lines each contain 2 integers $R_i, C_i$.

Output Format

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

3 2
1 2
2 2

7

Hint

• 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