시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1027 488 399 52.918%

문제

n행 n열의 격자로 나뉜 운동장이 있다. 이 위에 k개의 돌멩이가 있는데, 하나의 돌멩이는 격자 한 칸에 정확히 들어가 있으며, 두 개 이상의 돌멩이가 한 칸에 들어가 있는 경우는 없다.

사고의 위험을 없애기 위해 이 돌멩이들을 모두 제거하고 깨끗한 운동장을 만들려고 한다. 돌멩이들을 제거할 때에는, 한 행이나 한 열을 따라 직선으로 달려가면서 그 행이나 열에 놓인 돌멩이들을 모두 줍는 방식을 쓴다.

여러분이 할 일은 운동장의 상태가 주어졌을 때 최소 몇 번이나 달려가야 돌멩이 줍기를 끝낼 수 있는지 계산하는 것이다.

 

입력

첫째 줄에 n과 k가 주어진다. (1≤n≤500, 1≤k≤10,000) 이후 k개의 줄에는 돌멩이들의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째 숫자는 열 번호를 나타낸다.

출력

첫 줄에 몇 번의 달리기를 통해 돌멩이를 주울 수 있는지 출력한다.

예제 입력 1

3 4
1 1
1 3
2 2
3 2

예제 출력 1

2

힌트

돌멩이가 있는 곳은 X, 없는 곳은 _으로 표현하면 입력은 다음과 같다.

X _ X
_ X _
_ X _

1행을 따라 달리며 (1,1), (1,3)에 위치한 돌멩이를 줍는다. 2열을 따라 달리며 (2,2), (3,2)에 위치한 돌멩이를 줍는다. 두 번의 달리기로 작업을 완료할 수 있다.

W3sicHJvYmxlbV9pZCI6IjE4NjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzY2NcdWJhNjlcdWM3NzQgXHVjODFjXHVhYzcwIiwiZGVzY3JpcHRpb24iOiI8cD5uXHVkNTg5IG5cdWM1ZjRcdWM3NTggXHVhY2E5XHVjNzkwXHViODVjIFx1YjA5OFx1YjI1YyBcdWM2YjRcdWIzZDlcdWM3YTVcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjNzA0XHVjNWQwIGtcdWFjMWNcdWM3NTggXHViM2NjXHViYTY5XHVjNzc0XHVhYzAwIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVkNTU4XHViMDk4XHVjNzU4IFx1YjNjY1x1YmE2OVx1Yzc3NFx1YjI5NCBcdWFjYTlcdWM3OTAgXHVkNTVjIFx1Y2U3OFx1YzVkMCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHViNGU0XHVjNWI0XHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViNDUwIFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHViM2NjXHViYTY5XHVjNzc0XHVhYzAwIFx1ZDU1YyBcdWNlNzhcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYWNcdWFjZTBcdWM3NTggXHVjNzA0XHVkNWQ4XHVjNzQ0IFx1YzVjNlx1YzU2MFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNzc0IFx1YjNjY1x1YmE2OVx1Yzc3NFx1YjRlNFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjODFjXHVhYzcwXHVkNTU4XHVhY2UwIFx1YWU2OFx1YjA1N1x1ZDU1YyBcdWM2YjRcdWIzZDlcdWM3YTVcdWM3NDQgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViM2NjXHViYTY5XHVjNzc0XHViNGU0XHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU2MCBcdWI1NGNcdWM1ZDBcdWIyOTQsIFx1ZDU1YyBcdWQ1ODlcdWM3NzRcdWIwOTggXHVkNTVjIFx1YzVmNFx1Yzc0NCBcdWI1MzBcdWI3N2MgXHVjOWMxXHVjMTIwXHVjNzNjXHViODVjIFx1YjJlY1x1YjgyNFx1YWMwMFx1YmE3NFx1YzExYyBcdWFkZjggXHVkNTg5XHVjNzc0XHViMDk4IFx1YzVmNFx1YzVkMCBcdWIxOTNcdWM3NzggXHViM2NjXHViYTY5XHVjNzc0XHViNGU0XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM5MGRcdWIyOTQgXHViYzI5XHVjMmRkXHVjNzQ0IFx1YzRmNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWVjXHViN2VjXHViZDg0XHVjNzc0IFx1ZDU2MCBcdWM3N2NcdWM3NDAgXHVjNmI0XHViM2Q5XHVjN2E1XHVjNzU4IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjIFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHViYzg4XHVjNzc0XHViMDk4IFx1YjJlY1x1YjgyNFx1YWMwMFx1YzU3YyBcdWIzY2NcdWJhNjlcdWM3NzQgXHVjOTBkXHVhZTMwXHViOTdjIFx1YjA1ZFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHVhY2ZjIGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSZsZTtuJmxlOzUwMCwgMSZsZTtrJmxlOzEwLDAwMCkgXHVjNzc0XHVkNmM0IGtcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjY1x1YmE2OVx1Yzc3NFx1YjRlNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM5MDRcdWI5YzhcdWIyZTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVkNTg5IFx1YmM4OFx1ZDYzOCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjNWY0IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWJhODcgXHViYzg4XHVjNzU4IFx1YjJlY1x1YjlhY1x1YWUzMFx1Yjk3YyBcdWQxYjVcdWQ1NzQgXHViM2NjXHViYTY5XHVjNzc0XHViOTdjIFx1YzhmY1x1YzZiOCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHViM2NjXHViYTY5XHVjNzc0XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NDAgWCwgXHVjNWM2XHViMjk0IFx1YWNmM1x1Yzc0MCBfXHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YmE3NCBcdWM3ODVcdWI4MjVcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+WCBfIFg8YnIgXC8+XHJcbl8gWCBfPGJyIFwvPlxyXG5fIFggXzxcL3A+XHJcblxyXG48cD4xXHVkNTg5XHVjNzQ0IFx1YjUzMFx1Yjc3YyBcdWIyZWNcdWI5YWNcdWJhNzAgKDEsMSksICgxLDMpXHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU1YyBcdWIzY2NcdWJhNjlcdWM3NzRcdWI5N2MgXHVjOTBkXHViMjk0XHViMmU0LiAyXHVjNWY0XHVjNzQ0IFx1YjUzMFx1Yjc3YyBcdWIyZWNcdWI5YWNcdWJhNzAgKDIsMiksICgzLDIpXHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU1YyBcdWIzY2NcdWJhNjlcdWM3NzRcdWI5N2MgXHVjOTBkXHViMjk0XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjNzU4IFx1YjJlY1x1YjlhY1x1YWUzMFx1Yjg1YyBcdWM3OTFcdWM1YzVcdWM3NDQgXHVjNjQ0XHViOGNjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxODY3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQXN0ZXJvaWRzIiwiZGVzY3JpcHRpb24iOiI8cD5CZXNzaWUgd2FudHMgdG8gbmF2aWdhdGUgaGVyIHNwYWNlc2hpcCB0aHJvdWdoIGEgZGFuZ2Vyb3VzIGFzdGVyb2lkIGZpZWxkIGluIHRoZSBzaGFwZSBvZiBhbiBOIHggTiBncmlkICgxICZsdDs9IE4gJmx0Oz0gNTAwKS4gVGhlIGdyaWQgY29udGFpbnMgSyBhc3Rlcm9pZHMgKDEgJmx0Oz0gSyAmbHQ7PSAxMCwwMDApLCB3aGljaCBhcmUgY29udmVuaWVudGx5IGxvY2F0ZWQgYXQgdGhlIGxhdHRpY2UgcG9pbnRzIG9mIHRoZSBncmlkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3J0dW5hdGVseSwgQmVzc2llIGhhcyBhIHBvd2VyZnVsIHdlYXBvbiB0aGF0IGNhbiB2YXBvcml6ZSBhbGwgdGhlIGFzdGVyb2lkcyBpbiBhbnkgZ2l2ZW4gcm93IG9yIGNvbHVtbiBvZiB0aGUgZ3JpZCB3aXRoIGEgc2luZ2xlIHNob3QuVGhpcyB3ZWFwb24gaXMgcXVpdGUgZXhwZW5zaXZlLCBzbyBzaGUgd2lzaGVzIHRvIHVzZSBpdCBzcGFyaW5nbHkuR2l2ZW4gdGhlIGxvY2F0aW9uIG9mIGFsbCB0aGUgYXN0ZXJvaWRzIGluIHRoZSBmaWVsZCwgZmluZCB0aGUgbWluaW11bSBudW1iZXIgb2Ygc2hvdHMgQmVzc2llIG5lZWRzIHRvIGZpcmUgdG8gZWxpbWluYXRlIGFsbCBvZiB0aGUgYXN0ZXJvaWRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFR3byBpbnRlZ2VycyBOIGFuZCBLLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uSysxOiBFYWNoIGxpbmUgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBSIGFuZCBDICgxICZsdDs9IFIsIEMgJmx0Oz0gTikgZGVub3RpbmcgdGhlIHJvdyBhbmQgY29sdW1uIGNvb3JkaW5hdGVzIG9mIGFuIGFzdGVyb2lkLCByZXNwZWN0aXZlbHkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IFRoZSBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgbWluaW11bSBudW1iZXIgb2YgdGltZXMgQmVzc2llIG11c3Qgc2hvb3QuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2005-2006 Season > USACO November 2005 Contest > Gold 1번