캠핑장의 빈 울타리 구간

문제

캠핑장 관리인은 일직선 울타리를 따라 임시 장비를 놓을 자리를 찾고 있다. 울타리에는 왼쪽 끝부터 오른쪽 끝까지 0, 1, 2, …, L의 위치 표시가 있다. 서로 이웃한 두 표시 사이의 길이는 1이다. 장비를 놓을 수 있는 기본 단위는 이웃한 두 표시 사이의 한 칸이며, 왼쪽 위치가 x인 칸은 x번 칸이라고 부른다. 전체 울타리에는 0번부터 L-1번까지 총 L개의 칸이 있다. 현재 일부 칸은 예약되어 있다. 예약 기록 하나는 두 정수 l과 r로 주어지며, l번부터 r-1번까지의 칸을 모두 예약했다는 뜻이다. 이를 양 끝 위치가 l과 r인 구간이라고 부르며 길이는 r-l이다. 예약 기록은 입력 순서와 관계없이 적용된다. 서로 겹치는 기록이나 완전히 같은 기록이 여러 번 있어도 그 칸이 예약되었다는 사실만 유지한다. 관리인은 예약되지 않은 칸을 연속해서 가장 많이 사용할 수 있는 자리를 선택하려 한다. 선택한 자리의 양 끝 위치를 s와 e라고 하면 0 ≤ s < e ≤ L이어야 하며, s번부터 e-1번까지의 모든 칸이 예약되지 않아야 한다. 장비가 예약된 칸을 하나라도 포함해서는 안 된다. 선택하는 자리의 길이는 e-s이다. 가능한 자리 중 길이가 가장 긴 것을 선택한다. 가장 긴 자리가 여러 개이면 왼쪽 끝 위치 s가 가장 작은 것을 선택한다. 길이가 같고 s도 같으면 e 역시 같으므로 추가적인 동점 규칙은 필요 없다. 울타리 양 끝에 붙어 있는 빈자리도 후보에 포함한다. 예약이 하나도 없다면 울타리 전체를 선택한다. 반대로 모든 칸이 예약되어 길이가 양수인 자리가 없다면 -1을 출력한다. 선택한 자리의 양 끝은 반드시 정수 위치 표시여야 한다.

입력

첫째 줄에 정수 L과 N이 공백으로 구분되어 주어진다. 1 ≤ L ≤ 1000000000, 0 ≤ N ≤ 15000이다.
다음 N개 줄에 예약 기록을 나타내는 정수 l과 r이 공백으로 구분되어 주어진다. 모든 기록은 0 ≤ l < r ≤ L을 만족한다. 기록은 정렬되어 있지 않을 수 있으며, 서로 겹치거나 동일할 수 있다.

출력

선택할 수 있는 자리가 있으면 왼쪽 끝 위치 s와 오른쪽 끝 위치 e를 공백으로 구분하여 한 줄에 출력한다. 예약되지 않은 칸이 하나도 없으면 -1을 한 줄에 출력한다.

24 4
14 17
3 7
6 10
20 24

10 14

10 3
4 6
0 4
6 10

-1

9 0

0 9

출처: Devin.KR 자체 제작