Задача №112119. Хэдмастеры (A)
Уже скоро должен состояться финальный бой между трансформерами. Все вокруг затихло и ждет последнего сражения.
Давайте рассмотрим то, как готовятся к бою хэдмастеры. N хэдмастеров решили расположиться на N целых точках числовой прямой с координатами 1, 2, ..., N. В каждой точке должен оказаться ровно один робот. Единственная загвоздка заключается в том, что M различных пар роботов должны быть соединены специальными кабелями. Кабели являются очень дорогостоящими, поэтому стратегически важно минимизировать их суммарную длину.
Если робот в точке с координатой x должен быть соединен с роботом, который находится в точке с координатой y, то для их соединения потребуется |x - y| метров кабеля. Помогите хэдмастерам найти минимальное количество кабеля, которое необходимо потратить при оптимальном расположении роботов в указанных точках.
В первой строке входного файла записано два числа N (2 ≤ N ≤ 20) — количество хэдмастеров. Во второй строке находится одно целое число M — количество пар хэдмастеров, которые должны быть соединены. В следующих M строках заданы пары хэдмастеров, которые должны быть соединены. Пара задается ровно двумя натуральными числами, не превышающими N — номерами роботов. В каждой строке содержится ровно одна такая пара. Никакие две пары не совпадают.
Выведите в первую строку выходного файла выведите единственное число — минимальное количество кабеля, которое придется потратить хэдмастерам.
5
3
1 2
2 3
4 5
3
Первая группа тестов состоит из тестов, для которых выполняется ограничение N ≤ 10. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 баллов.
Первая группа тестов состоит из тестов, для которых выполняется ограничение N ≤ 16. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.
Третья группа тестов состоит из тестов, для которых выполняется ограничение N ≤ 20. Баллы за эту группу начисляются независимо. Стоимость группы составляет 40 баллов.
5 3 1 2 2 3 4 5
3