Minimum Observations to Cover All Trees

You are given an N × N grid and a set of trees located at certain coordinates within the grid. An observation can be made along an entire row or an entire column. In one observation, all trees in that row or column can be seen. Your task is to determine the minimum number of observations required such that every tree is observed.

Let \(R\) be the set of rows and \(C\) be the set of columns that contain at least one tree. The answer is \(\min(|R|, |C|)\).

Note that if there are no trees, no observation is needed.

inputFormat

The input is provided via standard input (stdin) in the following format:

N
M
x1 y1
x2 y2
... 
xM yM

Where:

• N is the size of the grid (note that the grid is N × N, though not all cells necessarily contain trees).
• M is the number of trees.
• Each of the following M lines contains two integers x and y, representing the coordinates of a tree. It is guaranteed that \(1 \leq x, y \leq N\).

outputFormat

Output via standard output (stdout) a single integer representing the minimum number of observations needed to see all trees.

4
0

0