Вам дан неориентированный граф из \(n\) вершин и \(m\) ребер. Вершины пронумерованы целыми числами от \(1\) до \(n\).
Назовем граф гармоничным если и только если выполняется следующее свойство:
- Для каждой такой тройки целых чисел \((l, m, r)\), что \(1 \le l < m < r \le n\), если есть путь из вершины \(l\) в вершину \(r\), тогда существует путь из вершины \(l\) в вершину \(m\).
Иначе говоря, в гармоничном графе, если из вершины \(l\) можно по ребрам дойти до вершины \(r\) (\(l < r\)), тогда также должно быть можно дойти до вершин \((l+1), (l+2), \ldots, (r-1)\).
Какое минимальное число ребер надо добавить в граф, чтобы он стал гармоничным?
Выходные данные
Выведите минимальное количество ребер которое нужно добавить в граф, чтобы он стал гармоничным.
Примечание
В первом примере граф не гармоничный (например, при \(1 < 6 < 7\), из вершины \(1\) можно достичь вершину \(7\) по пути \(1 \rightarrow 2 \rightarrow 7\), но из вершины \(1\) нельзя достичь вершину \(6\)). Однако добавление ребра \((2, 4)\) достаточно, чтобы сделать его гармоничным.
Во втором примере граф уже гармоничный.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12
|
1
|
|
2
|
200000 3
7 9
9 8
4 5
|
0
|