#1494. Asteroids 穿越小行星群

Asteroids 穿越小行星群

题目描述

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

输入格式

1行:两个整数N\red{N}K\red K,用一个空格隔开.

2行至K+1\red{K+1}行:每一行有两个空格隔开的整数RC(1RCN)\red{R,C(1≤R,C≤N)},分别表示小行星所在的行和列.

输出格式

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

输入样例

3 4
1 1
1 3
2 2
3 2

输出样例

2

提示

X.X
.X.
.X.

在第一行和第二例