Богдан та граф
Обмеження: 2 сек., 256 МіБ
Усі ми знаємо, що Богдан — успішний програміст. Під час участі в одному контесті Богдан зіткнувся із задачею на тему теорії графів. Оскільки теорія графів була однією з його не улюблених тем, він не зміг придумати жодного рішення до задачі. Чи можете ви допомогти Богдану й зробити його щасливим?
Вам задається неорієнтований граф з \(n\) вершин, пронумерованих від 1 до \(n\).
Тепер вам дозволяється робити дві операції.
Видалити ребро, яке є в графі.
Додати ребро між будь-якими двома вершинами графу.
Вартість вилучення або додавання ребра дорівнює \(|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 |
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|