시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB2189112791957.045%

문제

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+XHJcblxyXG48cD5cdWMwYWNcdWFjZTBcdWM3NTggXHVjNzA0XHVkNWQ4XHVjNzQ0IFx1YzVjNlx1YzU2MFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNzc0IFx1YjNjY1x1YmE2OVx1Yzc3NFx1Yjk3YyZuYnNwO1x1YmFhOFx1YjQ1MCBcdWM4MWNcdWFjNzBcdWQ1NThcdWFjZTAgXHVhZTY4XHViMDU3XHVkNTVjIFx1YzZiNFx1YjNkOVx1YzdhNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWIzY2NcdWJhNjlcdWM3NzRcdWI5N2MmbmJzcDtcdWM4MWNcdWFjNzBcdWQ1NjAgXHViNTRjXHVjNWQwXHViMjk0LCBcdWQ1NWMgXHVkNTg5XHVjNzc0XHViMDk4IFx1ZDU1YyBcdWM1ZjRcdWM3NDQgXHViNTMwXHViNzdjIFx1YzljMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWIyZWNcdWI4MjRcdWFjMDBcdWJhNzRcdWMxMWMgXHVhZGY4IFx1ZDU4OVx1Yzc3NFx1YjA5OCBcdWM1ZjRcdWM1ZDAgXHViMTkzXHVjNzc4IFx1YjNjY1x1YmE2OVx1Yzc3NFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjOTBkXHViMjk0IFx1YmMyOVx1YzJkZFx1Yzc0NCBcdWM0ZjRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc3NCBcdWQ1NjAgXHVjNzdjXHVjNzQwIFx1YzZiNFx1YjNkOVx1YzdhNVx1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmM4OFx1Yzc3NFx1YjA5OCBcdWIyZWNcdWI4MjRcdWFjMDBcdWM1N2MgXHViM2NjXHViYTY5XHVjNzc0IFx1YzkwZFx1YWUzMFx1Yjk3YyBcdWIwNWRcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHVhY2ZjIGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyA1MDAsIDEgJmxlOyBrICZsZTsgMTAsMDAwKSBcdWM3NzRcdWQ2YzQga1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2NjXHViYTY5XHVjNzc0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzkwNFx1YjljOFx1YjJlNCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWQ1ODkgXHViYzg4XHVkNjM4LCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM1ZjQgXHViYzg4XHVkNjM4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWIzY2NcdWJhNjlcdWM3NzRcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWJhODcgXHViYzg4XHVjNzU4IFx1YjJlY1x1YjlhY1x1YWUzMFx1Yjk3YyBcdWQxYjVcdWQ1NzQgXHViM2NjXHViYTY5XHVjNzc0XHViOTdjIFx1YzhmY1x1YzZiOCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHViM2NjXHViYTY5XHVjNzc0XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NDAgWCwgXHVjNWM2XHViMjk0IFx1YWNmM1x1Yzc0MCBfXHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YmE3NCBcdWM3ODVcdWI4MjVcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuWCBfIFhcclxuXyBYIF9cclxuXyBYIF88XC9wcmU+XHJcblxyXG48cD4xXHVkNTg5XHVjNzQ0IFx1YjUzMFx1Yjc3YyBcdWIyZWNcdWI5YWNcdWJhNzAgKDEsIDEpLCAoMSwgMylcdWM1ZDAgXHVjNzA0XHVjZTU4XHVkNTVjIFx1YjNjY1x1YmE2OVx1Yzc3NFx1Yjk3YyBcdWM5MGRcdWIyOTRcdWIyZTQuIDJcdWM1ZjRcdWM3NDQgXHViNTMwXHViNzdjIFx1YjJlY1x1YjlhY1x1YmE3MCAoMiwgMiksICgzLCAyKVx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NWMgXHViM2NjXHViYTY5XHVjNzc0XHViOTdjIFx1YzkwZFx1YjI5NFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1Yzc1OCBcdWIyZWNcdWI5YWNcdWFlMzBcdWI4NWMgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YzY0NFx1YjhjY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTg2NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFzdGVyb2lkcyIsImRlc2NyaXB0aW9uIjoiPHA+QmVzc2llIHdhbnRzIHRvIG5hdmlnYXRlIGhlciBzcGFjZXNoaXAgdGhyb3VnaCBhIGRhbmdlcm91cyBhc3Rlcm9pZCBmaWVsZCBpbiB0aGUgc2hhcGUgb2YgYW4gTiB4IE4gZ3JpZCAoMSAmbHQ7PSBOICZsdDs9IDUwMCkuIFRoZSBncmlkIGNvbnRhaW5zIEsgYXN0ZXJvaWRzICgxICZsdDs9IEsgJmx0Oz0gMTAsMDAwKSwgd2hpY2ggYXJlIGNvbnZlbmllbnRseSBsb2NhdGVkIGF0IHRoZSBsYXR0aWNlIHBvaW50cyBvZiB0aGUgZ3JpZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9ydHVuYXRlbHksIEJlc3NpZSBoYXMgYSBwb3dlcmZ1bCB3ZWFwb24gdGhhdCBjYW4gdmFwb3JpemUgYWxsIHRoZSBhc3Rlcm9pZHMgaW4gYW55IGdpdmVuIHJvdyBvciBjb2x1bW4gb2YgdGhlIGdyaWQgd2l0aCBhIHNpbmdsZSBzaG90LlRoaXMgd2VhcG9uIGlzIHF1aXRlIGV4cGVuc2l2ZSwgc28gc2hlIHdpc2hlcyB0byB1c2UgaXQgc3BhcmluZ2x5LkdpdmVuIHRoZSBsb2NhdGlvbiBvZiBhbGwgdGhlIGFzdGVyb2lkcyBpbiB0aGUgZmllbGQsIGZpbmQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHNob3RzIEJlc3NpZSBuZWVkcyB0byBmaXJlIHRvIGVsaW1pbmF0ZSBhbGwgb2YgdGhlIGFzdGVyb2lkcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gaW50ZWdlcnMgTiBhbmQgSywgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLksrMTogRWFjaCBsaW5lIGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgUiBhbmQgQyAoMSAmbHQ7PSBSLCBDICZsdDs9IE4pIGRlbm90aW5nIHRoZSByb3cgYW5kIGNvbHVtbiBjb29yZGluYXRlcyBvZiBhbiBhc3Rlcm9pZCwgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBUaGUgaW50ZWdlciByZXByZXNlbnRpbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHRpbWVzIEJlc3NpZSBtdXN0IHNob290LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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