Арио получил замечательный подарок на свой 2418-ый день рождения — набор интервалов! Он очень обрадовался и решил поскорее раскрасить все эти интервалы. Он использует простое правило. Раскраска называется красивой, если не существует трех интервалов a, b и c таких, что следующие условия выполняются одновременно:
Кроме того, он заметил, что для любых двух интервалов i и j, существует не менее одной точки в i, которая не принадлежит j.
Задан набор интервалов. Определите минимальное количество цветов k, необходимое для красивой раскраски.
Первая строка содержит целое положительное n (1 ≤ n ≤ 103) — количество интервалов. Далее в n строках содержатся описания интервалов, по одному в строке. Каждый интервал задается парой чисел si, ei, которые обозначают координаты его концов ( - 105 < si, ei < 105, si ≤ ei). Изучите примеры для лучшего понимания формата. Квадратная скобка в описании соответствует включению границы, а круглая — нет.
Выведите искомое минимальное число цветов k.
2 [1,2) (3,4]
1
3 [1,3] [2,6] (5,7)
2
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач