Descripción

Los concursantes del centro de entrenamiento le tomaron una fotografía a todos los ~N~ fanáticos del beisbol ~(2 \le N \le 1000000000)~, los cuales están en una fila convenientemente numerados de ~1~ a ~N~. Cada fotografía puede captar un rango consecutivo de fanáticos de la fila y los azucareros quieren estar seguro que cada fanático aparezca en al menos una foto. Desafortunadamente, hay K pares de fanáticos hostiles ~(1 \le K \le 1000)~ que rechazan estar en la misma foto.

Tarea

Dado los pares de fanáticos hostiles, escriba un programa photo que determine el número mínimo de fotos que los azucareros necesitan tomar.

Entrada

• Línea 1: Dos enteros separados por espacio, ~N~ y ~K~.

• Líneas ~2...K+1~: la línea ~i+1~ contiene dos enteros, ~Ai~ y ~Bi~, estableciendo que los fanáticos en las posiciones ~Ai~ y ~Bi~ son hostiles y por tanto no pueden estar en la misma fotografía.

Salida

• Línea 1: Un entero simple, especificando el número mínimo de fotos que los concursantes necesitan tomar.

Ejemplo Entrada

7 3
1 3
2 4
5 6

Ejemplo Salida

3

Detalles de la Salida

Los concursantes pueden tomar ~3~ fotos: - Una en el rango de ~1~ a ~2~, otra de ~3~ a ~5~ y otra de ~6~ a ~7~.