구간 그래프의 최대 클리크

그래프 이론에서 클리크는 완전 그래프인 부분 그래프를 말한다. 즉 정점 집합 중에서 두 정점을 어떻게 골라도 그 사이에 간선이 있는 집합이다. 최대 클리크는 그런 집합 중 크기가 가장 큰 것이다. 일반적인 그래프에서 최대 클리크를 구하는 문제는 NP-hard다.

$N$개의 구간이 있다. $i$번 구간의 시작점은 $S_i$, 끝점은 $E_i$이며, 두 구간이 점을 하나 이상 공유하면 두 구간이 겹친다고 한다. 이 구간들로 구간 그래프를 정의한다. 구간 그래프는 정점이 $N$개이고, $i$번 구간과 $j$번 구간이 겹칠 때만 $i$번 정점과 $j$번 정점 사이에 간선이 있는 그래프다. 두 구간이 겹치지 않으면 두 정점 사이에는 간선이 없다.

예를 들어 구간이 $[1, 3]$, $[3, 7]$, $[7, 10]$, $[2, 5]$로 주어지면 구간 그래프는 다음과 같다.

이 구간 그래프의 최대 클리크는 $\{1, 2, 4\}$다.

$N$개의 구간이 주어질 때 구간 그래프의 최대 클리크를 구하시오.

첫 줄에 구간의 수 $N$ ($1 \le N \le 300000$)이 주어진다. 다음 $N$개의 줄에 $i$번 구간의 시작점과 끝점을 나타내는 두 정수 $S_i$, $E_i$가 공백으로 구분되어 주어진다. ($1 \le S_i < E_i \le 10^9$)

첫 줄에 최대 클리크의 크기 $s$를 출력한다. 둘째 줄에는 그 클리크에 속한 정점의 번호 $s$개를 번호가 증가하는 순서로 공백으로 구분해 출력한다. 최대 클리크가 여러 개면 번호를 증가하는 순서로 나열한 목록이 사전순으로 가장 앞서는 클리크 하나를 출력한다.