Вам дано \(n\) цветных отрезков на числовой оси. Каждый отрезок либо красный, либо синий. Отрезок \(i\) описывается тройкой чисел \((c_i, l_i, r_i)\). Отрезок содержит все точки на отрезке \([l_i, r_i]\), включая концы, а его цвет описывается значением \(c_i\):
- если \(c_i = 0\), то это красный отрезок;
- если \(c_i = 1\), то это синий отрезок.
Скажем, что два отрезка различных цветов соединены, если они имеют хотя бы одну общую точку. Два отрезка принадлежат одной группе отрезков, если они соединены непосредственно или через цепочку соединенных непосредственно отрезок. Найдите число различных групп отрезков.
Выходные данные
Для каждого набора входных данных выведите одно целое число \(k\) — количество групп отрезков.
Примечание
В первом примере \(5\) отрезков. Отрезки \(1\) и \(2\) соединены, так как они различных цветов и имеют общую точку. Также отрезки \(2\) и \(3\) соединены, и отрезки \(4\) и \(5\) соединены. Таким образом, есть две группы: одна содержит отрезки \(\{1, 2, 3\}\), другая содержит отрезки \(\{4, 5\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5
0 0 5
1 2 12
0 4 7
1 9 16
0 13 19
3
1 0 1
1 1 2
0 3 4
|
2
3
|