eolymp
bolt
Try our new interface for solving problems
Problems

Интервалы

Интервалы

Time limit 2 seconds
Memory limit 64 MiB

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

Input data

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

Ограничения

1n1234

0mn(n-1)/2

Output data

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

Examples

Input example #1
3 2
0 1
1 2
Output example #1
4