Свято Фарби#6365

Свято Фарби

1 секунда

64 мегабайти

Дуже складна

Подорожуючи Південною Америкою, наші герої заїхали у державу Кольоровію, де саме святкували свято Фарби. На честь свята мешканці завжди проводили змагання на біговій доріжці стадіону, яку перед цим фарбували різними кольорами. У процесі фарбування приймали участь $N$ малярів і кожний з них фарбував своїм кольором, відмінним від іншого. Крім того кожний маляр знав який відрізок бігової доріжки він повинен пофарбувати. Але, оскільки процес фарбування проходив послідовно, то деякі ділянки бігової доріжки перефарбовувалися. Трохи поміркувавши Котигорошко знайшов таку послідовність роботи малярів, за якої, після закінчення усього процесу фарбування, кількість різних кольорів на доріжці буде максимальною.

Спробуйте і Ви це зробити.

Вхідні дані

Перший рядок містить ціле число $N$ ( $1 \leq N \leq 300$ 1 \leq N \leq 300). Наступні $N$ рядків містять по два цілих числа через пропуск. У $i$ -ому з цих рядків знаходяться числа $L_{i}$ L_i та $R_{i}$ R_i ( $- 1 0^{9} \leq L_{i} < R_{i} \leq 1 0^{9}$ -10^9 \leq L_i < R_i \leq 10^9), де $L_{i}$ L_i – початкова координата фарбування $i$ -ої ділянки; $R_{i}$ R_i – кінцева координата фарбування $i$ -ої ділянки.

Вихідні дані

У першому рядку треба вивести максимальну кількість кольорів, що буде видно на доріжці при оптимальному порядку фарбування.

У другому рядку повинно бути написано $N$ чисел – $i$ -е число позначає, який відрізок треба намалювати $i$ -им для досягнення оптимального результату.

Відрізки нумеруються, починаючи з одиниці, в тому ж порядку, в якому вони задані у вхідному файлі.

Приклади

Приклад 1

Примітка

За наявності декількох рішень вивести будь-яке з них.