Hide

Problem B
Holmes

Sherlock Holmes is a renowned detective. His Scotland Yard colleagues often provide him with a set of evidence and ask for his help in solving the mysteries. After many years of practice, Holmes has gained an enormous amount of experience and already knows causes for many common events, which, combined with his extraordinary deductive capabilities, enables him to solve cases in a matter of minutes, from the comfort of his chair.

Holmes’ knowledge base can be modeled as a set of implications of the form $A \rightarrow B$ (where $A$ and $B$ represent events), which means that, if $A$ occurred, event $B$ must have also occurred (remember that logical implication is false only if $A$ is true and $B$ is false). Of course, implications can form chains of reasoning, e.g., $A \rightarrow B \rightarrow C$. However, there will never be a circular chain of implications (e.g., $A \rightarrow B \rightarrow C \rightarrow \cdots \rightarrow A$).

Holmes is given a set $S = \{ S_1, S_2, S_3, \ldots , S_ n \} $ of events that are known to have occurred. He can then, using his extensive knowledge and deductive powers, find all events that have certainly occurred.

It’s important to note that Holmes’ knowledge is so mind-bogglingly huge that he knows all possible causes of events. In other words, there is no implication that is true, but not included in Holmes’ knowledge base. This means that if an event $A$ occurred and $A$ is known to be implied by some other event(s), then at least one of those other event(s) must have occurred as well.

Many detective agencies would highly appreciate Holmes’ one of a kind capabilities, so you were given a task to accomplish with a computer what is out of reach for ordinary mortals. Write a program to find all events that have certainly occurred based on the given implications and evidence collected by your colleague detectives.

Input

The first line of input consists of three integers, $D$ ($1 \le D \le 1000$), the number of different types of events, $M$ ($1 \le M \le 100\, 000$), the number of implications, and $N$ ($1 \le N \le D$), the number of events known to have occurred.

Each of the $M$ lines that follow contains two integers $A$ and $B$ ($1 \le A, B \le D$), describing an implication $A \rightarrow B$.

Finally, each of the last $N$ lines contains an integer $X$ ($1 \le X \le D$) describing an event that is known to have occurred, based on the evidence collected by detectives.

Output

The first and only line of output should contain integers (in increasing order) representing events that have certainly occurred.

Explanation of sample cases

In Sample Input 2, the knowledge base contains implications $1 \rightarrow 3$ and $2 \rightarrow 3$. Therefore, Holmes knows that event $3$ can be caused only by events $1$ and $2$, but (without any extra information), he can’t be certain which one of those events actually caused $3$. As a result, the only event that must have occurred is the one given in the input.

In Sample Input 3, Holmes doesn’t know which event from the set $\{ 2, 3\} $ is directly responsible for event $4$. However, as both of those events are caused only by event $1$, Holmes can deduce that event $1$ must have occurred. As a consequence, events $2$, $3$ and $4$ (given by the detectives) have also occurred.

Sample Input 1 Sample Output 1
3 2 1
1 2
2 3
2
1 2 3
Sample Input 2 Sample Output 2
3 2 1
1 3
2 3
3
3
Sample Input 3 Sample Output 3
4 4 1
1 2
1 3
2 4
3 4
4
1 2 3 4

Please log in to submit a solution to this problem

Log in