Farmer John хочет соединить $N$ сараев ($1 \le N \le 1{,}000$), номера $1..N$, новой оптоволоконной сетью. Они стоят по кругу вокруг большого пруда, поэтому соединять можно только соседние; сарай $N$ соседствует с 1.

Соединять все необязательно: общаться хотят только определённые пары коров. Нужен минимум связей, позволяющий общаться всем этим парам через сеть. По списку пар найдите минимум линий. Для связи 1 с 3 прокладывают линии 1-2 и 2-3.

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

• Строка $1$: целые $N$ и $P$, последнее — число пар ($1 \le P \le 10{,}000$).

• Строки $2..P+1$: два целых — пара сараев для связи. Повторных пар нет.

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

Одна строка с целым — минимальное число прямых соединений FJ.

Примеры

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

5 2
1 3
4 5

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

3

Примечание

Они соединяют пары сараев 1-2, 2-3 и 4-5.

Источник: Reid Barton, 2001.