Арио получил замечательный подарок на свой 2418-ый день рождения — набор интервалов! Он очень обрадовался и решил поскорее раскрасить все эти интервалы. Он использует простое правило. Раскраска называется красивой, если не существует трех интервалов a, b и c таких, что следующие условия выполняются одновременно:
- a, b и c покрашены в один цвет,
-
, -
, -
.
Кроме того, он заметил, что для любых двух интервалов i и j, существует не менее одной точки в i, которая не принадлежит j.
Задан набор интервалов. Определите минимальное количество цветов k, необходимое для красивой раскраски.
Выходные данные
Выведите искомое минимальное число цветов k.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
[1,2)
(3,4]
|
1
|
|
2
|
3
[1,3]
[2,6]
(5,7)
|
2
|