Farmer John veut assembler une photo panoramique de ses $N$ vaches alignées ($(1 \le N \le 200,000)$), numérotées comme toujours de $1..N$. Il prend $M$ photos ($(1 \le M \le 100,000)$), chacune couvrant un intervalle contigu : la photo $i$ contient les vaches $a_i$ à $b_i$ incluses. Ensemble, elles ne couvrent pas forcément chaque vache.

FJ remarque que chaque photo contient exactement une vache tachetée ! Il savait en avoir dans son troupeau, sans jamais les compter. Déterminez le nombre maximal possible de vaches tachetées selon les photos. S'il n'existe aucune attribution de taches compatible avec elles, affichez $-1$.

Entrée

• Ligne $1$ : entiers $N$ et $M$.

• Lignes $2..M+1$ : la ligne $i+1$ contient $a_i$ et $b_i$.

Sortie

• Ligne $1$ : nombre maximal possible de vaches tachetées, ou $-1$ si aucune solution n'existe.

Exemples

Entrée 1

5 3
1 4
2 5
3 4

Sortie 1

1

Remarque

Il y a $5$ vaches et $3$ photos. La première contient les vaches $1$ à $4$, etc.

La dernière photo indique que la vache $3$ ou $4$ doit être tachetée. Choisir l'une ou l'autre satisfait aussi les deux premières photos.

Auteur du problème : Brian Dean, 2013