D. Гармоничный граф
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан неориентированный граф из $$$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)$$$.

Какое минимальное число ребер надо добавить в граф, чтобы он стал гармоничным?

Входные данные

В первой строке входного файла записаны два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 200\ 000$$$ и $$$1 \le m \le 200\ 000$$$).

В $$$i$$$-й из следующих $$$m$$$ строк записаны два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), описывающих ребро между вершинами $$$u$$$ и $$$v$$$.

Гарантируется, что граф простой (в нем нет петель, а также между каждой парой вершин существует не более одного ребра).

Выходные данные

Выведите минимальное количество ребер которое нужно добавить в граф, чтобы он стал гармоничным.

Примеры
Входные данные
14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12
Выходные данные
1
Входные данные
200000 3
7 9
9 8
4 5
Выходные данные
0
Примечание

В первом примере граф не гармоничный (например, при $$$1 < 6 < 7$$$, из вершины $$$1$$$ можно достичь вершину $$$7$$$ по пути $$$1 \rightarrow 2 \rightarrow 7$$$, но из вершины $$$1$$$ нельзя достичь вершину $$$6$$$). Однако добавление ребра $$$(2, 4)$$$ достаточно, чтобы сделать его гармоничным.

Во втором примере граф уже гармоничный.