Mafia

A mafia group is trying to move through a highway network from a starting tollgate to a destination tollgate. The network consists of n tollgates and m bidirectional highways. Cars cannot enter or leave in the middle of a highway, so every route must pass only through tollgates and highways.

Each tollgate has an occupation cost. You may occupy some tollgates, except for the starting tollgate and the destination tollgate, so that the group cannot travel from the start to the destination without passing through an occupied tollgate.

Find the tollgates to occupy while minimizing the total occupation cost.

The first line contains the number of tollgates n and the number of highways m. (1 <= n <= 200, 1 <= m <= 20,000) Tollgates are numbered from 1 to n.

The second line contains the starting tollgate s and the destination tollgate t. The next n lines contain the occupation costs of tollgates 1 through n, one per line. Each cost is a positive integer not greater than 10,000,000.

The final m lines each contain two tollgates a and b connected by a highway. Every highway can be traveled in both directions.

Print, in increasing order on one line, the numbers of the tollgates selected with minimum total occupation cost.

If no tollgate needs to be printed, print an empty line.