Farmer John chce złożyć panoramiczne zdjęcie szeregu $N$ krów ($(1 \le N \le 200,000)$), jak zawsze ponumerowanych od $1..N$. Zrobił $M$ zdjęć ($(1 \le M \le 100,000)$), każde obejmuje spójny przedział: zdjęcie $i$ zawiera krowy od $a_i$ do $b_i$ włącznie. Razem zdjęcia nie muszą obejmować wszystkich krów.

FJ zauważa, że każde zdjęcie zawiera dokładnie jedną łaciatą krowę! Wiedział, że w stadzie są takie krowy, lecz nigdy ich nie policzył. Wyznacz maksymalną możliwą liczbę łaciatych krów na podstawie zdjęć. Jeśli nie można przypisać łat zgodnie ze zdjęciami, wypisz $-1$.

Wejście

• Wiersz $1$: całkowite $N$ i $M$.

• Wiersze $2..M+1$: wiersz $i+1$ zawiera $a_i$ i $b_i$.

Wyjście

• Wiersz $1$: maksymalna możliwa liczba łaciatych krów lub $-1$, gdy brak rozwiązania.

Przykład

Wejście 1

5 3
1 4
2 5
3 4

Wyjście 1

1

Uwagi

Jest $5$ krów i $3$ zdjęcia. Pierwsze obejmuje krowy $1$ do $4$ itd.

Ostatnie wskazuje, że krowa $3$ albo $4$ musi być łaciata. Wybór dowolnej z nich spełnia także pierwsze dwa zdjęcia.

Autor zadania: Brian Dean, 2013