Removing Stones

A playground is divided into an n by n grid. There are k stones on the playground. Each stone occupies exactly one cell, and no cell contains more than one stone.

To remove stones, you choose one row or one column at a time, run straight along it, and pick up every stone in that row or column.

Given the state of the playground, find the minimum number of runs needed to pick up all stones.

The first line contains two integers n and k. (1 <= n <= 500, 1 <= k <= 10,000)

Each of the next k lines contains the position of one stone. The first integer is the row number, and the second integer is the column number. All given positions are distinct.

Print the minimum number of runs needed to pick up all stones.

If a cell with a stone is marked X and an empty cell is marked _, one possible arrangement is:

X _ X_ X __ X _

Running along row 1 picks up the stones at (1, 1) and (1, 3). Then running along column 2 picks up the stones at (2, 2) and (3, 2), so all stones can be removed in two runs.