시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 242 42 23 16.667%

문제

홍준이는 한국에서 손에 꼽히는 부자 중 한 명이다. 홍준이의 집은 N개의 방이 원형으로 나열된 형식으로 구성되어 있다. 홍준이는 자신의 집에 K개의 감시 카메라를 설치했다. 각 감시 카메라는 원형으로 나열된 방들 중 일부 연속된 구간을 감시한다. 홍준이는 모든 방을 다 감시하고 싶어 하는데, 이미 설치된 K개의 감시 카메라 중 몇 개는 필요하지 않다는 것을 깨달았다.

홍준이의 방은 1번 방부터 N번 방까지 원형으로 배열되어 있다. 즉, 1번 방 양 옆에는 2번 방과 N번 방이 있고, N번 방 양 옆에는 N-1번 방과 1번 방이 있다.

K개의 감시 카메라가 감시하는 구간에 대한 정보가 주어졌을 때, 모든 방을 감시하기 위해 필요한 최소 감시 카메라 개수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 방의 개수 N과 감시 카메라의 개수 K가 주어진다. (3 ≤ N ≤ 106, 1 ≤ K ≤ 106)

다음 K개의 줄에 각 감시 카메라에 대한 정보 ai와 bi가 주어진다. (1 ≤ ai, bi, ≤ N)

ai ≤ bi 인 경우, ai ≤ j ≤ bi 를 만족하는 j번 방이 감시 받는다는 것을 의미하고, ai > bi 인 경우, 1 ≤ j ≤ bi 혹은 ai ≤ j ≤ N 을 만족하는 j번 방이 감시 받는다는 것을 의미한다.

출력

홍준이가 모든 방을 감시하기 위해 필요한 감시 카메라의 최소 개수를 출력한다. 만약, 모든 방을 감시하는 것이 불가능하다면,  impossible을 출력한다.

예제 입력 1

100 7
1 50
50 70
70 90
90 40
20 60
60 80
80 20

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjEwMDYwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhYzEwXHVjMmRjIFx1Y2U3NFx1YmE1NFx1Yjc3YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNjRkXHVjOTAwXHVjNzc0XHViMjk0IFx1ZDU1Y1x1YWQ2ZFx1YzVkMFx1YzExYyBcdWMxOTBcdWM1ZDAgXHVhZjNkXHVkNzg4XHViMjk0IFx1YmQ4MFx1Yzc5MCBcdWM5MTEgXHVkNTVjIFx1YmE4NVx1Yzc3NFx1YjJlNC4gXHVkNjRkXHVjOTAwXHVjNzc0XHVjNzU4IFx1YzlkMVx1Yzc0MCBOXHVhYzFjXHVjNzU4IFx1YmMyOVx1Yzc3NCBcdWM2ZDBcdWQ2MTVcdWM3M2NcdWI4NWMgXHViMDk4XHVjNWY0XHViNDFjIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWQ2NGRcdWM5MDBcdWM3NzRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzlkMVx1YzVkMCBLXHVhYzFjXHVjNzU4IFx1YWMxMFx1YzJkYyBcdWNlNzRcdWJhNTRcdWI3N2NcdWI5N2MgXHVjMTI0XHVjZTU4XHVkNTg4XHViMmU0LiBcdWFjMDEgXHVhYzEwXHVjMmRjIFx1Y2U3NFx1YmE1NFx1Yjc3Y1x1YjI5NCBcdWM2ZDBcdWQ2MTVcdWM3M2NcdWI4NWMgXHViMDk4XHVjNWY0XHViNDFjIFx1YmMyOVx1YjRlNCBcdWM5MTEgXHVjNzdjXHViZDgwIFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWFkNmNcdWFjMDRcdWM3NDQgXHVhYzEwXHVjMmRjXHVkNTVjXHViMmU0LiBcdWQ2NGRcdWM5MDBcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YmMyOVx1Yzc0NCBcdWIyZTQgXHVhYzEwXHVjMmRjXHVkNTU4XHVhY2UwIFx1YzJmNlx1YzViNCBcdWQ1NThcdWIyOTRcdWIzNzAsIFx1Yzc3NFx1YmJmOCBcdWMxMjRcdWNlNThcdWI0MWMgS1x1YWMxY1x1Yzc1OCBcdWFjMTBcdWMyZGMgXHVjZTc0XHViYTU0XHViNzdjIFx1YzkxMSBcdWJhODcgXHVhYzFjXHViMjk0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWU2OFx1YjJlY1x1YzU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjRkXHVjOTAwXHVjNzc0XHVjNzU4IFx1YmMyOVx1Yzc0MCAxXHViYzg4IFx1YmMyOVx1YmQ4MFx1ZDEzMCBOXHViYzg4IFx1YmMyOVx1YWU0Y1x1YzljMCBcdWM2ZDBcdWQ2MTVcdWM3M2NcdWI4NWMgXHViYzMwXHVjNWY0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjOTg5LCAxXHViYzg4IFx1YmMyOSBcdWM1OTEgXHVjNjA2XHVjNWQwXHViMjk0IDJcdWJjODggXHViYzI5XHVhY2ZjIE5cdWJjODggXHViYzI5XHVjNzc0IFx1Yzc4OFx1YWNlMCwgTlx1YmM4OCBcdWJjMjkgXHVjNTkxIFx1YzYwNlx1YzVkMFx1YjI5NCBOLTFcdWJjODggXHViYzI5XHVhY2ZjIDFcdWJjODggXHViYzI5XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+S1x1YWMxY1x1Yzc1OCBcdWFjMTBcdWMyZGMgXHVjZTc0XHViYTU0XHViNzdjXHVhYzAwIFx1YWMxMFx1YzJkY1x1ZDU1OFx1YjI5NCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViYzI5XHVjNzQ0IFx1YWMxMFx1YzJkY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWFjMTBcdWMyZGMgXHVjZTc0XHViYTU0XHViNzdjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHViYzI5XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVhY2ZjIFx1YWMxMFx1YzJkYyBcdWNlNzRcdWJhNTRcdWI3N2NcdWM3NTggXHVhYzFjXHVjMjE4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAxMDxzdXA+NjxcL3N1cD4sJm5ic3A7MSAmbGU7IEsgJmxlOyAxMDxzdXA+NjxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDEgXHVhYzEwXHVjMmRjIFx1Y2U3NFx1YmE1NFx1Yjc3Y1x1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0IGE8c3ViPmk8XC9zdWI+XHVjNjQwIGI8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEmbmJzcDsmbGU7IGFpLCBiaSwmbmJzcDsmbGU7IE4pPFwvcD5cclxuXHJcbjxwPmE8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyBiPHN1Yj5pPFwvc3ViPiBcdWM3NzggXHVhY2JkXHVjNmIwLCBhPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsgaiZuYnNwOyZsZTsgYjxzdWI+aTxcL3N1Yj4mbmJzcDtcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IGpcdWJjODggXHViYzI5XHVjNzc0IFx1YWMxMFx1YzJkYyBcdWJjMWJcdWIyOTRcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YWNlMCwgYTxzdWI+aTxcL3N1Yj4gJmd0OyBiPHN1Yj5pPFwvc3ViPiZuYnNwO1x1Yzc3OCBcdWFjYmRcdWM2YjAsIDEmbmJzcDsmbGU7IGombmJzcDsmbGU7IGI8c3ViPmk8XC9zdWI+IFx1ZDYzOVx1Yzc0MCBhPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsgaiZuYnNwOyZsZTsgTiBcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IGpcdWJjODggXHViYzI5XHVjNzc0IFx1YWMxMFx1YzJkYyBcdWJjMWJcdWIyOTRcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ2NGRcdWM5MDBcdWM3NzRcdWFjMDAgXHViYWE4XHViNGUwIFx1YmMyOVx1Yzc0NCBcdWFjMTBcdWMyZGNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWFjMTBcdWMyZGMgXHVjZTc0XHViYTU0XHViNzdjXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YmFhOFx1YjRlMCBcdWJjMjlcdWM3NDQgXHVhYzEwXHVjMmRjXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWJhNzQsJm5ic3A7IDxjb2RlPmltcG9zc2libGU8XC9jb2RlPlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTAwNjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdXJ2ZWlsbGFuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBJbnRlcm5hdGlvbmFsIENvcnBvcmF0aW9uIGZvciBQcm90ZWN0aW9uIGFuZCBDb250cm9sIChJQ1BDKSBkZXZlbG9wcyBlZmZpY2llbnQgdGVjaG5vbG9neSBmb3IsIHdlbGwsIHByb3RlY3Rpb24gYW5kIGNvbnRyb2wuIE5hdHVyYWxseSwgdGhleSBhcmUga2VlbiB0byBoYXZlIHRoZWlyIG93biBoZWFkcXVhcnRlcnMgcHJvdGVjdGVkIGFuZCBjb250cm9sbGVkLiBWaWV3ZWQgZnJvbSBhYm92ZSwgdGhlIGhlYWRxdWFydGVycyBidWlsZGluZyBoYXMgdGhlIHNoYXBlIG9mIGEgY29udmV4IHBvbHlnb24uIFRoZXJlIGFyZSBzZXZlcmFsIHN1aXRhYmxlIHBsYWNlcyBhcm91bmQgaXQgd2hlcmUgY2FtZXJhcyBjYW4gYmUgaW5zdGFsbGVkIHRvIG1vbml0b3IgdGhlIGJ1aWxkaW5nLiBFYWNoIGNhbWVyYSBjb3ZlcnMgYSBjZXJ0YWluIHJhbmdlIG9mIHRoZSBwb2x5Z29uIHNpZGVzIChidWlsZGluZyB3YWxscyksIGRlcGVuZGluZyBvbiBpdHMgcG9zaXRpb24uIElDUEMgd2FudHMgdG8gbWluaW1pemUgdGhlIG51bWJlciBvZiBjYW1lcmFzIG5lZWRlZCB0byBjb3ZlciB0aGUgd2hvbGUgYnVpbGRpbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgdGVzdCBjYXNlLiBJdHMgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgbiBhbmQgayAoMyAmbGU7IG4gJmxlOyAxMDxzdXA+NjxcL3N1cD4gYW5kIDEgJmxlOyBrICZsZTsgMTA8c3VwPjY8XC9zdXA+KSwgd2hlcmUgbiBpcyB0aGUgbnVtYmVyIG9mIHdhbGxzIGFuZCBrIGlzIHRoZSBudW1iZXIgb2YgcG9zc2libGUgcGxhY2VzIGZvciBpbnN0YWxsaW5nIGNhbWVyYXMuIEVhY2ggb2YgdGhlIHJlbWFpbmluZyBrIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBhPHN1Yj5pPFwvc3ViPiBhbmQgYjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4gJmxlOyBuKS4gVGhlc2UgaW50ZWdlcnMgc3BlY2lmeSB3aGljaCB3YWxscyBhIGNhbWVyYSBhdCB0aGUgaTxzdXA+dGg8XC9zdXA+IHBsYWNlIHdvdWxkIGNvdmVyLiBJZiBhPHN1Yj5pPFwvc3ViPiAmbGU7IGI8c3ViPmk8XC9zdWI+IHRoZW4gdGhlIGNhbWVyYSBjb3ZlcnMgZWFjaCB3YWxsIGogc3VjaCB0aGF0IGE8c3ViPmk8XC9zdWI+ICZsZTsgaiAmbGU7IGI8c3ViPmk8XC9zdWI+LiBJZiBhPHN1Yj5pPFwvc3ViPiAmZ3Q7IGI8c3ViPmk8XC9zdWI+IHRoZW4gdGhlIGNhbWVyYSBjb3ZlcnMgZWFjaCB3YWxsIGogc3VjaCB0aGF0IGE8c3ViPmk8XC9zdWI+ICZsZTsgaiAmbGU7IG4gb3IgMSAmbGU7IGogJmxlOyBiPHN1Yj5pPFwvc3ViPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5EaXNwbGF5IHRoZSBtaW5pbWFsIG51bWJlciBvZiBjYW1lcmFzIHRoYXQgc3VmZmljZSB0byBjb3ZlciBlYWNoIHdhbGwgb2YgdGhlIGJ1aWxkaW5nLiBUaGUgcmFuZ2VzIGNvdmVyZWQgYnkgdHdvIGNhbWVyYXMgbWF5IG92ZXJsYXAuIElmIHRoZSBidWlsZGluZyBjYW5ub3QgYmUgY292ZXJlZCwgZGlzcGxheSA8Y29kZT5pbXBvc3NpYmxlPFwvY29kZT4gaW5zdGVhZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > World Finals > 2014 World Finals K번