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

1 T N*N

1 R[i], C[i] N

For all 1 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.