Farmer John vuole collegare $N$ stalle ($1 \le N \le 1{,}000$), numerate $1..N$, con fibra ottica. Circondano un grande stagno in cerchio, quindi si collegano solo vicine; la stalla $N$ è vicina alla 1.

Non deve collegarle tutte: solo certe coppie di mucche vogliono comunicare. Vuole il minimo di collegamenti che permetta tutte le comunicazioni nella rete. Date le coppie, trova il minimo di linee. Per comunicare da 1 a 3 occorrono linee 1-2 e 2-3.

Input

• Riga $1$: interi $N$ e $P$, quest'ultimo è il numero di coppie ($1 \le P \le 10{,}000$).

• Righe $2..P+1$: due interi per una coppia di stalle che vuole comunicare. Nessuna coppia ripetuta.

Output

Una riga con un intero, minimo di collegamenti diretti necessari.

Esempi

Input 1

5 2
1 3
4 5

Output 1

3

Note

Collegano le coppie 1-2, 2-3 e 4-5.

Crediti: Reid Barton, 2001.