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 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.

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.

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 evidence collected by the detectives.

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 must have occurred, based on the evidence collected by detectives.

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

Explanation of the second sample case: 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.

Explanation of the third sample case: 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\) have also occurred.

riseoj 작성

출처 COCI 2009/2010 Contest 6