USACO 2005 November Gold, poj3041 Asteroids- 우주여행 > 문제은행 : 정보올림피아드&알고리즘




1882 : 우주여행

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
8 회   
시도횟수
10 회   

문제

농부 창호가 키우는 소 중 가장 영리한 소 베시는 우주선을 타고 N x N(1≤N≤500)짜리 격자 안에 있는 위험한 소행성 구역을 지나가려고 한다.

그 격자 안에는 K(1 ≤ K ≤ 10,000)개의 소행성이 있는데, 편리하게도 모두 격자점 위에 위치하고 있다.



다행스럽게도, 베시는 강력한 무기를 가지고 있다. 그 무기는 어떤 주어진 행이나 열에 있는 모든 소행성을 한방에 증발시킬 수 있다.

이 무기는 매우 비싸기 때문에 그녀는 이것을 알뜰하게 사용하기를 원한다. 

구역 안에 있는 모든 소행성의 위치가 주어졌을 때, 베시가 모든 소행성을 제거하기 위해서 무기를 최소한 몇 번 사용해야 하는 지를 구하라.


입력형식

입력의 첫 번째 줄에는 두 개의 정수 N, K가 하나의 공백으로 나누어져 들어온다. 두 번째 줄부터 K+1번째 줄에는 공백으로 나누어진 두 개의 수 R, C(1 ≤ R, C ≤ N)가 들어오며, 두 수 R, C는 각각 소행성의 행과 열을 나타낸다.

출력형식

베시에게 필요한 최소한의 무기 사용 횟수를 출력한다.

입력 예

3 4
1 1
1 3
2 2
3 2

출력 예

2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP