도서관 예약 묶음 검사

문제

한 도서관은 하나의 독립 열람실을 예약제로 운영한다. 백엔드 담당자는 외부에서 전달받은 예약 묶음을 저장하기 전에, 그 안에 서로 충돌하는 예약이 있는지 검사하는 기능을 만들고 있다. 이번 검사에서는 전달받은 N개의 예약만 확인하며, 이미 저장된 다른 예약은 고려하지 않는다. 입력에 적힌 예약 순서는 이용 시각이나 신청 순서와 관계없다. 각 예약에는 시작 시각 S와 종료 시각 E가 있다. 시각은 도서관이 정한 공통 기준 순간부터 지난 분을 정수로 나타낸 값이다. 날짜를 별도로 계산할 필요는 없으며, 두 시각은 주어진 정수의 크기로 비교한다. 모든 예약은 시작 시각보다 종료 시각이 늦다. 예약자는 시작 시각을 포함하고 종료 시각을 포함하지 않는 구간 동안 열람실을 사용한다. 한 예약이 끝나는 시각에 다른 예약이 시작되는 것은 허용한다. 예를 들어 12분부터 18분까지의 예약과 18분부터 25분까지의 예약은 함께 저장할 수 있다. 반면 12분부터 18분까지의 예약과 17분부터 20분까지의 예약은 열람실을 함께 사용하는 시간이 있으므로 충돌한다. 두 예약의 사용 구간이 양의 길이만큼 겹치면 두 예약이 충돌한다고 정의한다. 한 예약이 다른 예약에 완전히 포함된 경우도 충돌이다. 시작 시각과 종료 시각이 모두 같은 예약이 여러 번 들어오면 각각 별개의 예약으로 취급하므로 이들 역시 충돌한다. 시작 시각이 같은 예약의 입력 순서에 따른 우선권은 없다. 담당자가 필요한 결과는 충돌하는 예약의 목록이나 개수가 아니라, 묶음 전체를 그대로 저장할 수 있는지 여부다. 충돌하는 두 예약이 하나라도 있으면 CONFLICT를 출력하고, 모든 예약을 함께 저장할 수 있으면 OK를 출력한다. 예약이 하나뿐인 묶음은 항상 OK다.

입력

첫째 줄에 예약 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 20,000이다.
다음 N개의 줄에 각 예약의 시작 시각 S와 종료 시각 E가 공백으로 구분되어 주어진다. S와 E는 정수이며 0 ≤ S < E ≤ 1,000,000이다. 예약은 임의의 순서로 주어진다.

출력

서로 충돌하는 예약이 하나라도 있으면 CONFLICT를 출력한다. 없으면 OK를 출력한다. 영문 대문자를 그대로 사용한다.

4
30 40
0 10
20 30
10 20

OK

3
40 60
5 50
70 80

CONFLICT

2
15 22
15 22

CONFLICT

출처: Devin.KR 자체 제작