Farmer John will ein Panoramafoto seiner $N$ in einer Reihe stehenden Kühe ($(1 \le N \le 200,000)$) zusammensetzen, wie immer von $1..N$ nummeriert. Er macht $M$ Fotos ($(1 \le M \le 100,000)$), jedes von einem zusammenhängenden Bereich: Foto $i$ enthält Kühe $a_i$ bis $b_i$ einschließlich. Zusammen müssen die Fotos nicht jede Kuh erfassen.

FJ bemerkt, dass jedes Foto genau eine gefleckte Kuh enthält! Er wusste, dass es einige in seiner Herde gibt, hatte sie aber nie gezählt. Bestimme anhand der Fotos die maximal mögliche Zahl gefleckter Kühe. Ist keine Zuordnung von Flecken mit den Fotos vereinbar, gib $-1$ aus.

Eingabe

• Zeile $1$: ganze Zahlen $N$ und $M$.

• Zeilen $2..M+1$: Zeile $i+1$ enthält $a_i$ und $b_i$.

Ausgabe

• Zeile $1$: maximal mögliche Zahl gefleckter Kühe, oder $-1$, wenn keine Lösung existiert.

Beispiele

Eingabe 1

5 3
1 4
2 5
3 4

Ausgabe 1

1

Hinweis

Es gibt $5$ Kühe und $3$ Fotos. Das erste enthält Kühe $1$ bis $4$ usw.

Aus dem letzten Foto folgt, dass entweder Kuh $3$ oder $4$ gefleckt sein muss. Jede dieser Wahlen erfüllt auch die ersten beiden Fotos.

Aufgabenautor: Brian Dean, 2013