Hannah está construyendo una estructura hecha de malvaviscos y pinchos para su clase de química. La estructura contendrá ~N~ malvaviscos, numerados de ~1~ a ~N~. Algunos malvaviscos estarán conectados por pinchos. Cada pincho conecta dos malvaviscos.

Hannah tiene requisitos ~M~ para su estructura. Cada requisito se da como un par ~(a_i, b_i)~, lo que significa que debe haber un pincho que conecte el malvavisco ~a_i~ y el malvavisco ~b_i~.

Para asegurar la estabilidad de la estructura, también se debe cumplir el siguiente requisito: si ~a < b < c~, y si hay un pincho que conecta el malvavisco ~a~ con el malvavisco ~b~, y si hay un pincho que conecta el malvavisco ~a~ con el malvavisco ~c~, entonces también debe haber un pincho que conecte al malvavisco ~b~ con el malvavisco ~c~.

Debido a las medidas de austeridad impuestas por la oficina del director, los pinchos son escasos en la escuela de Hannah. Encuentre el número mínimo de pinchos necesarios para satisfacer todos los requisitos.

Especificación de entrada

La primera línea contiene dos números enteros separados por espacios ~N~ y ~M~ ~(1 \le N, M \le 10^5)~.

Las siguientes ~M~ líneas contienen cada una dos enteros separados por espacios, con la ~i~-ésima línea que contiene ~a_i~ y ~b_i~ ~(1 \leq a_i < b_i \leq N)~. Todos los ~M~ pares ~(a_i, b_i)~ son distintos.

Subtareas

Subtarea 1 (18 puntos), ~N \le 100~.

Subtarea 2 (39 puntos), ~N \le 5000~.

Subtarea 3 (28 puntos), para todo ~1 \le j \le N~, hay como máximo un par ~(a_i, b_i)~ tal que ~b_i = j~.

Subtarea 4 (15 puntos) Sin restricciones adicionales.

Especificación de salida

Salida de un solo entero, el número total mínimo de pinchos.

Entrada de muestra 1

6 4
1 2
1 4
4 6
4 5

Salida para entrada de muestra 1

6

Explicación de la salida para la entrada de muestra 1

Además de los ya requeridos, debe haber pinchos entre los pares de malvaviscos ~(2, 4)~ y ~(5, 6)~.

Entrada de muestra 2

7 6
2 3
2 6
2 7
1 3
1 4
1 5

Salida para entrada de muestra 2

16