Farmer John veut relier $N$ granges ($1 \le N \le 1{,}000$), numérotées $1..N$, par fibre optique. Elles entourent un grand étang en cercle, donc seules les voisines peuvent être reliées ; la grange $N$ est voisine de 1.

Il n'a pas besoin de tout relier : seules certaines paires de vaches veulent communiquer. Il veut le minimum de connexions permettant toutes ces communications à travers le réseau. À partir des paires demandées, trouvez le minimum de lignes. Pour communiquer de 1 à 3, on pose des lignes 1-2 et 2-3.

Entrée

• Ligne $1$ : entiers $N$ et $P$, ce dernier étant le nombre de paires ($1 \le P \le 10{,}000$).

• Lignes $2..P+1$ : deux entiers désignant une paire de granges devant communiquer. Aucune paire répétée.

Sortie

Une ligne avec un entier, nombre minimal de connexions directes nécessaires.

Exemples

Entrée 1

5 2
1 3
4 5

Sortie 1

3

Remarque

Elles relient les paires de granges 1-2, 2-3 et 4-5.

Source : Reid Barton, 2001.