# Los prerrequisitos de una malla La oficina académica revisa una malla curricular: una lista de cursos, cada uno con un código, y una lista de prerrequisitos. Un prerrequisito `A B` significa que el curso A tiene que estar aprobado antes de llevar el curso B. Quieren saber en cuántos semestres, como mínimo, se puede terminar la malla. Un curso se puede llevar en un semestre si todos sus prerrequisitos se aprobaron en semestres anteriores. **No hay límite de cursos por semestre**, y se supone que quien lleva un curso lo aprueba. La malla también puede estar mal escrita. Un curso está **atrapado en un ciclo** si es prerrequisito de sí mismo, ya sea directamente (`A A`) o a través de otros cursos (`A B`, `B C`, `C A`). Dicho de otra forma: siguiendo prerrequisitos desde ese curso se puede volver a él. Un curso que solo depende de un curso atrapado no está atrapado: tampoco se puede llevar nunca, pero corregir el ciclo lo arregla sin tocarlo. Cuando hay cursos atrapados, nadie termina la malla, y la oficina quiere la lista de esos cursos, y solo de esos, para corregirla. ## Entrada La primera línea tiene dos enteros: n, la cantidad de cursos, y m, la cantidad de prerrequisitos. La segunda parte son n líneas con un código cada una, todos distintos. Luego vienen m líneas, cada una con dos códigos `A B`: A es prerrequisito de B. Un mismo prerrequisito puede aparecer más de una vez. Todo código de un prerrequisito aparece en la lista de cursos. ## Salida - Si ningún curso está atrapado, una línea con el mínimo de semestres. - Si hay cursos atrapados, una línea `CICLO t`, donde t es cuántos son, y luego t líneas con sus códigos, **en el mismo orden en que aparecen en la lista de cursos de la entrada**. ## Límites - 1 ≤ n ≤ 300 000 - 0 ≤ m ≤ 600 000 - Cada código tiene de 1 a 10 caracteres, entre letras sin tilde y dígitos. ## Ejemplo Entrada: ```text 5 5 MAT1 PROG1 PROG2 ALGO BD MAT1 ALGO PROG1 PROG2 PROG2 ALGO PROG2 BD MAT1 BD ``` Salida: ```text 3 ``` PROG1 y MAT1 se llevan en el primer semestre, PROG2 en el segundo, y ALGO y BD en el tercero. No se puede en menos, porque PROG1, PROG2 y ALGO tienen que ir en semestres distintos. Otra entrada: ```text 5 5 SO ARQ REDES TESIS FIS ARQ SO SO ARQ REDES REDES SO TESIS FIS SO ``` Salida: ```text CICLO 3 SO ARQ REDES ``` SO y ARQ se piden entre sí, y REDES se pide a sí mismo. TESIS depende de SO, y FIS es prerrequisito de SO, pero ninguno de los dos está en un ciclo. ## La malla de la carrera Uno de los casos (`casos/12.in`) es la propuesta de malla de la carrera. Incluye solo los 27 cursos de Ciencia de la Computación, con sus códigos, porque de los demás la propuesta no da códigos. Para escribirla en este formato se tomaron estas decisiones, que son del curso y no de la propuesta: - Los prerrequisitos de otros departamentos (Cálculo, Álgebra Lineal, Cálculo multivariable) no se cuentan. - CS802 pide "6.º semestre aprobado". Se escribió como: todos los cursos de CS hasta el semestre 6 son prerrequisito de CS802. Basta listar seis, porque los demás ya son prerrequisito de alguno de ellos: CS501, CS504, CS601, CS602, CS603 y CS604. - Los cuatro electivos (CS803, CS902, CS903 y CS1002) tienen prerrequisito "según línea", que depende de la línea que cada quien elija. Están en la lista, sin prerrequisitos. Antes de correr su programa con este caso, adivinen la respuesta. ¿Coincide con los 10 semestres del plan? ¿Por qué? ## Tiempo 3 segundos por caso, compilado con `-O2`. Corran `make test` para probar con el juez. Un programa que termina con `RE` en un caso grande sin error aparente quizá agotó la pila. En el juez, la pila es la que tiene el contenedor por defecto (en bash, `ulimit -s` da 8192 KB).