Problem Description

Translated from COCI 2010.03.20 T5 “HOLMES”.

There are $D$ events, numbered $1\ldots D$.

Holmes has $M$ inferences of the form $A\rightarrow B$, meaning “if event $A$ happens, then event $B$ will definitely happen”. Note that this does not mean “if $A$ does not happen, then $B$ will definitely not happen”.

These $M$ inferences can form chain structures, such as $A\rightarrow B\rightarrow C$, but they will never form a cycle, such as $A\rightarrow B\rightarrow C\rightarrow \dots \rightarrow A$.

It is known that events $S_1\ldots S_N$ will happen. Find which events will definitely happen.

Update: The original statement is unclear (or maybe my reading is poor), so here is one extra sentence to explain sample 1. For an event $X$, if there exist inferences $Y_1\rightarrow X,$ $Y_2\rightarrow X$, then “event $X$ will definitely happen” if and only if “event $Y_1$ will definitely happen” or “event $Y_2$ will definitely happen” ……

Input Format

The first line: $D, M, N$.
The next $M$ lines: each line contains two integers, representing one inference $A_i, B_i$.
The next $N$ lines: the $i$-th line contains one integer $S_i$.

Output Format

One line with several integers, representing the events that will definitely happen.

Output in any order is acceptable Please output them in increasing order of event number, because the uploader was too lazy to write an SPJ.

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

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

3 4

Hint

Explanation for Sample 2

If we only know that event 3 happens, we cannot deduce whether event 1 caused event 3 or event 2 caused event 3.

Explanation for Sample 3

If event 4 happens, then at least one of events 2 and 3 happens;
no matter which one happens, its condition is that event 1 definitely happens;
since event 1 definitely happens, events 2 and 3 both definitely happen.

Explanation for Sample 4

If event 3 happens, then at least one of events 1 and 2 definitely happens;
if either event 1 or event 2 happens, then event 4 will definitely happen.

Constraints and Hints

$1\le D\le 1000,$ $1\le M\le 10^5,$ $1\le N,$ $X_i,$ $A_i,$ $B_i\le D$.

Translated by ChatGPT 5