P7368 [USACO05NOV] Asteroids G

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.

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 one integer per line, representing the minimum cost to remove all asteroids.

#### Sample Explanation: The sample grid is (where `X` represents an asteroid): ```text 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