MOG Round #2Ended |
Fito no está saliendo muy bien en la escuela porque se pasa todo el tiempo jugando DOTA , así que decidió que antes de jugar siempre iba a terminar las tareas. Hoy Fito tiene que hacer la tarea de lógica , pero está muy difícil y hasta que no la termine no podrá jugar, por lo que te pidió que lo ayudaras a resolverla.
La tarea consta de un conjunto de N eventos, un conjunto de M causas de eventos de la forma A->B (si ocurre el evento A entonces ocurre el evento B ), donde A y B son dos eventos del conjunto y un conjunto de T eventos que se sabe que han ocurrido. Se sabe además que las causas de eventos no forman ninguna cadena circular , por ejemplo A->B->C->A .
Fito tiene que decir todos los eventos que él puede deducir que han ocurrido, sabiendo que las únicas causas de eventos posibles son las que él tiene.
Los eventos están numerados desde 1 hasta N
La primera línea contiene 3 enteros N,M y T (1<=N<=1000, 1<= M<=100000,1<=T<=N), la cantidad de distintos tipos de eventos que existen, la cantidad de causas de eventos y la cantidad de eventos que se sabe que han ocurrido.
En cada una de las M siguientes líneas habrá dos enteros A,B que representan que el evento A implica al evento B.
A continuación habrá T líneas cada una con un entero 1<= x <=N que indica que Fito sabe que el evento x ha ocurrido.
Una línea con enteros separados por un espacio, que contenga la lista de eventos que se puede deducir que ocurrieron, ordenados de forma creciente .
Explicación del ejemplo 2:
Fito sabe que 1->3 y 2->3, así que sabe que 3 solo puede ser causado por 1 o por 2, pero sin más información no se puede deducir cual de estos eventos debe ocurrir. Por lo tanto el único evento que se puede deducir que ocurre es 3.
Explicación del ejemplo 3:
Fito sabe que uno de los dos eventos 2 o 3 tiene que ocurrir para que 4 pueda ocurrir, pero como estos dos eventos solo son causados por 1, Fito debe deducir que 1 tiene que ocurrir. Así que se puede deducir que deben ocurrir 1,2,3 y 4