eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Интервалы

Интервалы

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

На вещественной прямой отмечено n интервалов. Концы каждого интервала попадают в целые точки. При этом концы интервалов не принадлежат им. Известно, какие отрезки пересекаются, а какие нет. По этой информации необходимо определить, какая может быть минимальная суммарная длина всех отрезков. Также интервалы не могут иметь нулевую длину (т.е. длина каждого из них должна быть хотя бы 1).

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

В первой строке входа даны числа n количество интервалов, и m количество пересечений между интервалами. Далее в m строках указаны пары пересекающихся интервалов. Интервалы нумеруются числами от 0 до n-1. Если какая-та пара интервалов не указана, значит они не пересекаются. Гарантируется, что по данной информации можно построить набор интервалов соответствующий ей.

Ограничения

1n1234

0mn(n-1)/2

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

Выведите минимально возможную суммарную длину всех интервалов. Интервалы не могут иметь нулевую длину.

Пример

Входные данные #1
3 2
0 1
1 2
Выходные данные #1
4