Problem Description

Bessie wants to fly her spaceship in an $N \times N$ grid. There are $K$ asteroids in the grid. To make the flight enjoyable, she must remove all of these asteroids.

Bessie has a weapon that can remove all asteroids in one row or one column at a cost of one unit. Bessie wants to know the minimum cost to remove all asteroids.

Input Format

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

The next $K$ lines each contain $x_i, y_i$, representing the coordinates of the $i$-th asteroid in the grid.

Output Format

Output one integer per line, representing the minimum cost to remove all asteroids.

3 4
1 1
1 3
2 2
3 2

2

Hint

Sample Explanation:

The sample grid is (where X represents an asteroid):

X.X
.X.
.X.

Bessie can remove the asteroids by removing the first row and the second column.

Constraints:

For $100\%$ of the testdata, $1 \leq N \leq 500$, $1 \leq K \leq N \times N$.

Translated by ChatGPT 5