Malvaviscos


Submit solution


Points: 100 (partial)
Time limit: 7.0s
Memory limit: 512M

Authors:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Prolog, Python, Swift, VB

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

Comments

There are no comments at the moment.