Minimum Toll Booth Control Set

The police in Byteland want to intercept a gang transporting contraband along the highway network. The network is modeled as an undirected graph where nodes represent toll booths and edges represent highway segments. Each toll booth i has an associated monitoring cost \(c_i\). The gang enters the highway at toll booth \(s\) (closest to the port) and exits at toll booth \(t\) (closest to the warehouse). A highway path from \(s\) to \(t\) is intercepted if it passes through at least one monitored toll booth.

The task is to determine the minimum control set of toll booths such that every \(s\)-\(t\) path contains at least one toll booth from this set, and the sum of the monitoring costs is minimized.

Hint (Vertex Splitting): This problem can be transformed into a minimum \(s\)-\(t\) cut problem on a directed graph. For each toll booth \(i\), split it into two nodes \(i_{in}\) and \(i_{out}\) and add an edge from \(i_{in}\) to \(i_{out}\) with capacity \(c_i\). For each undirected edge connecting \(u\) and \(v\) in the original graph, add two directed edges: one from \(u_{out}\) to \(v_{in}\) and another from \(v_{out}\) to \(u_{in}\) with infinite capacity (or a value large enough, e.g. \(10^9\)). After computing the minimum cut from \(s_{in}\) to \(t_{out}\), any toll booth \(i\) for which \(i_{in}\) is reachable from \(s_{in}\) in the residual graph but \(i_{out}\) is not, must be monitored.

You may assume there is always at least one path from \(s\) to \(t\>.

inputFormat

The input is given from standard input as follows:

1. The first line contains two integers \(n\) and \(m\) where \(n\) is the number of toll booths and \(m\) is the number of highway segments.
2. The second line contains \(n\) integers where the \(i\)th integer represents the cost \(c_i\) to monitor toll booth \(i\) (\(1 \le i \le n\)).
3. The next \(m\) lines each contain two integers \(u\) and \(v\), indicating that there is a bidirectional highway segment connecting toll booths \(u\) and \(v\). It is guaranteed that \(u \neq v\) and no highway segment appears more than once.
4. The last line contains two integers \(s\) and \(t\), representing the toll booth closest to the port (the entry) and the toll booth closest to the warehouse (the exit), respectively.

outputFormat

Output a set of toll booth numbers (separated by spaces) that form the minimum control set. The order of toll booths in the output does not matter.

sample

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

1