隔离带

Grade 100 Open Time Thursday, 18 June 2020, 6:00 PM
Discount 0.8 Time Discount Thursday, 18 June 2020, 6:00 PM
Allow late Yes Close Time Thursday, 18 June 2020, 6:00 PM
Input file Asteroids.in Output file Asteroids.out

【题目描述】隔离带(Asteroids)POJ 3041

星际战队奉命在星系外围建立一条一百光年宽的隔离带,隔离带中的所有小行星将被摧毁。摧毁工作是分段进行的,例如在某个n×n的空间内,分布着k个小行星,战舰的能量炮,每启动一次可以清除某一行或某一列的小行星,但启动一次能量炮耗费的能量巨大,所以舰长希望你能计算出启动能量炮的最少次数。

【输入数据】

第一行为两个整数n和k((1≤n≤500,1≤k≤10 000)。随后k行中,每行有两个整数R和C (1 ≤R,C≤N)表示小行星的坐标。

【输出数据】

输出一个数,即最少次数。

【输入样例】

3 4

1 1

1 3

2 2

3 2

【输出样例】

2