페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#1882

우주여행 1초 64MB

문제

농부 창호가 키우는 소 중 가장 영리한 소 베시는 우주선을 타고 N x N (1≤N≤500)짜리 격자 안에 있는 위험한 소행성 구역을 지나가려고 한다. 그 격자 안에는 K (1 ≤ K ≤ 10\,000)개의 소행성이 있는데, 편리하게도 모두 격자점 위에 위치하고 있다.

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

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

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


입력

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


출력

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

예제1

입력
34

11

13

22

32
출력
2

출처

USACO 2005 November Gold, poj3041 Asteroids

역링크