Farmer John chce połączyć $N$ stodół ($1 \le N \le 1{,}000$), numerowanych $1..N$, światłowodem. Stoją w kole wokół dużego stawu, więc można łączyć tylko sąsiednie; stodoła $N$ sąsiaduje z 1.

Nie trzeba łączyć wszystkich: tylko pewne pary krów chcą rozmawiać. Potrzeba minimum połączeń umożliwiających wszystkim tym parom rozmowę przez sieć. Ze spisu par znajdź minimum linii. Do komunikacji 1 z 3 trzeba ułożyć 1-2 oraz 2-3.

Wejście

• Wiersz $1$: całkowite $N$ i $P$, drugie to liczba par ($1 \le P \le 10{,}000$).

• Wiersze $2..P+1$: dwie całkowite dla pary stodół wymagających komunikacji. Pary nie powtarzają się.

Wyjście

Jeden wiersz z całkowitą, minimum bezpośrednich połączeń.

Przykład

Wejście 1

5 2
1 3
4 5

Wyjście 1

3

Uwagi

Łączą pary stodół 1-2, 2-3 oraz 4-5.

Źródło: Reid Barton, 2001.