Задача I. Художнег

Автор:Жюри летних сборов 2009   Ограничение времени:2 сек
Входной файл:painter.in   Ограничение памяти:256 Мб
Выходной файл:painter.out  
Максимальный балл:100  

Условие

Художник Вася Ниимович рисует абстрактные картины. Новая его картина выглядит как прямая, части которой раскрашены в разные цвета. Рисовал он её так. Вначале он нарисовал отрезок первого цвета от точки l1 до точки r1. Потом отрезок второго цвета от l2 до r2, и так далее. Последний отрезок, нарисованный им, проходил от ln до rn и имел цвет с номером n.

Все отрезки были разных цветов, однако некоторые оказались полностью закрашены другими. Тогда Вася задумался: возможно, если бы он рисовал отрезки в тех же местах, но в другом порядке, то различных цветов на картине было бы больше? Помогите ему выбрать такой порядок рисования отрезков, при котором после того, как он нарисует все отрезки, количество видимых цветов на картине будет максимально. Отрезки считаются замкнутыми.

Формат входного файла

В первой строке написано целое число n. В следующих n строках будут написаны по два целых числа через пробел. В i-ой из этих строк находятся числа li и ri.

Формат выходного файла

В первой строке выведите количество цветов, которые будут видны при оптимальном порядке рисования. Во второй строке должно быть написано n чисел — i-ое число обозначает, какой отрезок надо нарисовать i-ым для достижения оптимального результата. Отрезки нумеруются, начиная с единицы, в том же порядке, в котором они заданы во входном файле.

Ограничения

1 ≤ n ≤ 300;

109 ≤ li ≤ ri ≤ 109

Примеры тестов

Входной файл (painter.in) Выходной файл (painter.out)
1
4 
1 3
2 4
2 3
1 4
3
4 1 2 3

0.035s 0.007s 15