Farmer John möchte $N$ Scheunen ($1 \le N \le 1{,}000$), nummeriert $1..N$, mit Glasfaser verbinden. Sie stehen im Kreis um einen großen Teich, daher können nur Nachbarn verbunden werden; Scheune $N$ ist Nachbar von 1.

Nicht alle müssen verbunden sein: nur bestimmte Kuhpaare möchten kommunizieren. Er will möglichst wenige Verbindungen, aber alle gewünschten Gespräche über das Netz ermöglichen. Finde aus den Paaren die minimale Leitungszahl. Für Kommunikation von 1 zu 3 müssen 1-2 und 2-3 verlegt werden.

Eingabe

• Zeile $1$: ganze Zahlen $N$ und $P$, letzteres ist die Paarzahl ($1 \le P \le 10{,}000$).

• Zeilen $2..P+1$: zwei ganze Zahlen für ein gewünschtes Scheunenpaar. Keine Paarwiederholung.

Ausgabe

Eine Zeile mit einer ganzen Zahl, minimale Anzahl direkter Verbindungen.

Beispiele

Eingabe 1

5 2
1 3
4 5

Ausgabe 1

3

Hinweis

Sie verbinden die Scheunenpaare 1-2, 2-3 und 4-5.

Aufgabenquelle: Reid Barton, 2001.