Space Asteroids Eradication

Bessie is piloting her spaceship on an \(N \times N\) grid scattered with \(K\) asteroids. In order to have a pleasant ride, she must eliminate all the asteroids. She has a weapon that, at a cost of one unit, can eliminate all asteroids in an entire row or an entire column.

Your task is to determine the minimum cost required to eliminate all asteroids. Formally, each asteroid located at \((r, c)\) can be removed by either eliminating row \(r\) or column \(c\). This is a classic instance of the bipartite vertex cover problem. By Kőnig's theorem, the minimum cost is equal to the size of the maximum matching in the bipartite graph where the two parts are the rows and columns (only those that contain asteroids) and there is an edge between a row and a column if an asteroid exists at that cell.

The input provides \(N\), \(K\), and the positions of the asteroids. Compute the size of the maximum matching.

inputFormat

The first line contains two integers \(N\) and \(K\) (\(1 \leq N \leq 10^5\), \(0 \leq K \leq 10^5\)) representing the grid size and the number of asteroids respectively. Each of the following \(K\) lines contains two integers \(r\) and \(c\) (1-indexed) indicating the position of an asteroid.

outputFormat

Output a single integer: the minimum cost to remove all asteroids (i.e. the size of the maximum matching in the bipartite graph).

sample

3 3
1 1
1 2
2 2

2