P5191 [COCI 2009/2010 #6] HOLMES

**Translated from [COCI 2010.03.20](http://hsin.hr/coci/archive/2009_2010/) T5 “[HOLMES](http://hsin.hr/coci/archive/2009_2010/contest6_tasks.pdf)”.** 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” ……

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

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.

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