该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

贝茜想驾驶她的飞船穿过危险的小行星群．小行星群是一个$\red{N \times N}$的网格$\red {(1≤N≤500)}$，在网格内有K个小行星($\red{1≤K≤10000}$)． 幸运地是贝茜有一个很强大的武器，一次可以消除所有在一行或一列中的小行星，这种武器很贵，所以她希望尽量地少用．给出所有的小行星的位置，算出贝茜最少需要多少次射击就能消除所有的小行星．

输入格式

第1行：两个整数$\red{N}$和$\red K$，用一个空格隔开．

第2行至$\red{K+1}$行：每一行有两个空格隔开的整数$\red{R，C(1≤R，C≤N)}$，分别表示小行星所在的行和列．

输出格式

一个整数表示贝茜需要的最少射击次数，可以消除所有的小行星

输入样例

3 4
1 1
1 3
2 2
3 2

输出样例

2

提示

X.X
.X.
.X.

在第一行和第二例