Праздник Краски
Путешествуя по Южной Америке, наши герои заехали в страну Красочную, где как раз праздновали праздник Краски. На честь праздника жители всегда проводили соревнования на беговой дорожке стадиона, которую перед этим красили разными цветами. В процессе покраски принимали участие N маляров и каждый из них красил своим цветом, отличным от другого. Кроме того каждый маляр знал какой отрезок беговой доржки он должен покрасить. Но, так как процесс покраски происходил последовательно, то некоторые участки беговой дорожки перекрашивались. Немного подумав Котигорошко нашел такую последовательность работы маляров, при которой, после завершения всего процесса покраски количество разных цветов на дорожке будет максимальным.
Попробуйте и Вы это сделать.
Входные данные
Первая строка содержит целое число N (1 ≤ N ≤ 300). Следующие N строк содержат по два целых числа через пробел. В i-ой из этих строк находятся числа L_{і} и R_{і} (–10^9 ≤ L_{і} < R_{і} ≤ 10^9), где L_{і} – начальная координата покраски i-ого участка; R_{і} – конечная координата покраски i-ого участка.
Выходные данные
В первой строке необходимо вывести максимальное количество цветов, которое будет видно на дорожке при оптимальном порядке покраски.
Во второй строке должно быть записано N чисел – i-ое число означает, какой отрезок нужно красить i-ым для достижения оптимального результат.
Отрезки нумеруются, начиная с единицы, в том же порядке, в котором они заданы во входном файле.
Примечание. При наличии нескольких решений вывести любое из них.