Богдан та граф

Обмеження: 2 сек., 256 МіБ

Усі ми знаємо, що Богдан — успішний програміст. Під час участі в одному контесті Богдан зіткнувся із задачею на тему теорії графів. Оскільки теорія графів була однією з його не улюблених тем, він не зміг придумати жодного рішення до задачі. Чи можете ви допомогти Богдану й зробити його щасливим?

Вам задається неорієнтований граф з $n$ вершин, пронумерованих від 1 до $n$.

Тепер вам дозволяється робити дві операції.

1. Видалити ребро, яке є в графі.

2. Додати ребро між будь-якими двома вершинами графу.

Вартість вилучення або додавання ребра дорівнює $|u - v|$, де $u$ й $v$ — кінці ребра, яке додається або видаляється.

Виконувати операції можна скільки завгодно разів.

Знайдіть мінімальну ціну, необхідну для перетворення цього графу в одне дерево.

Вхідні дані

Перший рядок містить два цілих числа $n$ і $m$ — кількості вершин і ребер відповідно.

У наступних $m$ рядках задано по два цілих числа $u$, $v$, які означають ребро з кінцями $u$ й $v$.

Вихідні дані

У єдиному рядку виведіть ціле число — необхідну мінімальну вартість.

Обмеження

$1 \le n, m \le 10^6$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 5 1 2 2 3 3 4 4 5 1 3	1