COCI 2009/2010, Contest #6

Task 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 → 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 → B → C). However, there will never be a circular chain of implications (e.g. A → B → C → ... → A).

Holmes is given a set S = {S₁, S₂, S₃, ..., 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.

Input

The first line of input consists of three integers, D (1 ≤ D ≤ 1000), the number of different types of events, M (1 ≤ M ≤ 100 000), the number of implications, and N (1 ≤ N ≤ D), the number of evidence collected by the detectives.

Each of the M lines that follow contains two integers A and B (1 ≤ A, B ≤ D), describing an implication A → B.

Finally, each of the last N lines contain an integer X (1 ≤ X ≤ D) describing an event that must have occurred, based on the evidence collected by detectives.

Output

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

Sample Tests

3 2 1
1 2
2 3
2

1 2 3

3 2 1
1 3
2 3
3

3

4 4 1
1 2
1 3
2 4
3 4
4

1 2 3 4

Explanation of Sample 2

The knowledge base contains implications 1 → 3 and 2 → 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, only event that must have occurred is the one given in the input.

Explanation of Sample 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.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Jul 09, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

5 6 1
1 2
3 2
1 4
3 4
2 5
4 5
5
output ?