Description

The police in Byteland received an anonymous report saying that the local mafia boss is planning a transport from the port to a warehouse in the suburbs. The police know the time of the transport, and they know that the transport will use the country's highway network.

The highway network consists of bidirectional highway segments, and each segment directly connects two different toll stations. A toll station may be connected to many other toll stations. Cars can enter or leave the highway network only through toll stations. It is known that the mafia will enter the highway at the toll station closest to the port and leave at the toll station closest to the warehouse (they will not re-enter the highway after leaving). A special police unit will be stationed at selected toll stations. When the transport vehicle enters a monitored toll station, it will be caught by the police.

From this point of view, the simplest way is to station a police unit at every toll station. However, controlling a toll station requires a certain cost, and the costs differ between stations. The police want the minimum total cost, so they need to determine a minimum control set of toll stations that satisfies two conditions:

• Every route from the port to the warehouse must pass through at least one toll station in the set.
• The total monitoring cost of these toll stations (i.e., the sum of the costs of all toll stations in the set) is minimal.

You may assume that it is possible to travel from the port to the warehouse using the highway network.

Task

Write a program that:

• reads the highway network, monitoring costs, and the start and end points of the transport from standard input;
• finds a minimum control set of toll stations;
• outputs this set to standard output.

Input Format

The first line of standard input contains two integers $n$ and $m$, representing the total number of toll stations and the total number of highway segments. Toll stations are numbered from $1$ to $n$.

The second line contains two integers $a$ and $b$, representing the indices of the toll stations closest to the port and the warehouse, respectively.

The next $n$ lines describe the control costs. Line $i+2$ contains one integer, representing the control cost $c_i$ of toll station $i$.

The next $m$ lines describe the highway network. Line $j+n+2$ contains two integers $x_j$ and $y_j$, meaning there is a highway segment connecting toll stations $x_j$ and $y_j$. Each highway segment appears only once.

Output Format

The only line of output should contain the indices of the toll stations in the minimum control set, in increasing order, separated by one space.

If there is more than one minimum control set, your program may output any one of them.

5 6
5 3
2
4
8
3
10
1 5
1 2
2 4
4 5
2 3
3 4

1 4

Hint

Sample Explanation

This image shows the toll station indices (in the top-left corner) and the control costs in the highway network. Toll stations $1$ and $4$ form a minimum control set, with a total control cost of $5$.

Constraints

For $40\%$ of the testdata, $n\le 20$.

For all testdata, $1\le n\le 200$, $1\le m\le 2\times 10^4$, $1\le a,b\le n$, $a\not= b$, $1\le c_i\le 10^7$, $1\le x_j<y_j\le n$.

Translated by ChatGPT 5