#P5954. Event Propagation Deduction

    ID: 19179 Type: Default 1000ms 256MiB

Event Propagation Deduction

Event Propagation Deduction

In the world of JSOI, there are \(N\) distinct events numbered from \(1\) to \(N\) and \(M\) clues. Each clue is represented as a pair \((x,y)\) indicating that if event \(x\) occurs, then event \(y\) will also occur.

Note: The clues are one-directional; that is, the occurrence of event \(y\) does not imply the occurrence of event \(x\). The clues are also transitive, meaning that if both \((x,y)\) and \((y,z)\) exist, then the occurrence of event \(x\) forces event \(z\) to occur.

Furthermore, the world is consistent: no set of clues can cause an event to trigger itself. Moreover, because the world only contains these \(M\) clues, no event occurs spontaneously. In particular, if an event \(x\) occurs and there exists some event that can possibly trigger \(x\), then at least one such triggering event must have occurred.

Given the \(M\) clues and \(D\) events that are known to have occurred, determine which events must inevitably have occurred by the propagation rules.

inputFormat

The input consists of:

  • The first line contains two integers \(N\) and \(M\) separated by a space.
  • The next \(M\) lines each contain two integers \(x\) and \(y\), representing a clue that if event \(x\) occurs then event \(y\) occurs.
  • The following line contains an integer \(D\), the number of events that have occurred.
  • The last line contains \(D\) distinct integers, each representing an event that has occurred.

outputFormat

Output all events that must have occurred, in increasing order, separated by a single space.

sample

3 2
1 2
2 3
1
1
1 2 3