| Unknown Language Round 3 |
|---|
| Закончено |
- Pike 7.8
Арио получил замечательный подарок на свой 2418-ый день рождения — набор интервалов! Он очень обрадовался и решил поскорее раскрасить все эти интервалы. Он использует простое правило. Раскраска называется красивой, если не существует трех интервалов a, b и c таких, что следующие условия выполняются одновременно:
- 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
