Question:Voldemort has now cast a new kind of spell named 'Illusio'. This
spell creates the illusion that he is at multiple locations at the same time.
Since Harry does not know the location of the real Voldemort, he must destroy
all his illusions in order to win.
Assume there is a 2-dimensional square grid with illusions spread across
it. Outside the grid, on the boundary, stands Harry Potter. Harry can quickly
reach the exterior of any row or column and cast a spell which will destroy all
the illusions in that row or column. Realizing that he has very little strength
left, he must cast as few spells as possible and destroy all the illusions.
Your job is to help him determine the minimum number of spells he will need to
destroy all the illusions in the grid and win the duel.
Input
The first line of the input contains an integer N denoting
the length of the square grid.
The second line contains an integer T denoting the
total number of illusions in the grid.
Then follow T lines, the ith of which contains 2
space-separated integers R[i] and C[i] denoting the
(1-based) row and column coordinates of the ith illusion.
Output
A single integer denoting the minimum number of spells
needed to destroy all of Voldemort's illusions as per the problem statement.
Constraints
1 <= N <= 100
1 <= T <= N*N
1 <= R[i], C[i] <= N
For all 1 <= i < j <= T, either R[i]!=R[j] or C[i]!=C[j],
that is to say that the locations of all the T illusions are distinct
Example
Input:
4
3
1 3
2 1
4 3
Output:
2
Explanation
Since the illusions at (1,3) and (4,3) are both located in
column 3, they can be destroyed with a single spell if Harry casts it on column
3. The illusion at (2,1) can be destroyed with another spell either by casting
it on row 2 or column 1. This makes a total of 2 spells. It is easy to see that
2 is the least possible number.