题目描述

题目译自 BalticOI 2008 Day0「Mafia」

Byteland 国警方收到了一条匿名举报，其中说当地黑帮老大正计划一次从港口到郊区仓库的运输。警方知道运输的时间并且知道运输需要用到国家的高速公路网。
高速公路网包含双向的高速公路段，每个路段直接连着两个不同的收费站。一个收费站可能与很多其他的收费站相连。汽车只能通过收费站进入或离开高速公路网。据所知，黑帮会距港口边最近的收费站进入高速公路，从距仓库最近的收费站离开（不会在出高速后重新进入）。特警组位于选定的收费站处。当运输车辆进入被监控的收费站时，它就会被警察抓住。
从这个角度看，最简单的办法就是在每个收费站处都安排特警班。然而，控制一个收费站需要特定的费用，每个收费站费用不同。警方想要让花费最小，所以他们需要制定一个收费站的最小控制集，这个集合满足两个条件：

• 所有从港口到仓库的交通必须至少经过集合中的一个收费站
• 监控这些收费站的费用（即监控每一个收费站费用之和）最小

你可以假设使用高速公路可以从港口到仓库。

任务

写一个程序能够：

• 从标准输入中读取高速公路网，监控代价和运输的起点和终点
• 找到收费站的最小控制集
• 输出这个集合到标准输出

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$，表示收费站的总数和公路段的总数。收费站按 $1$ 到 $n$ 标号；
第二行包含两个整数 $a$ 和 $b$，分别表示距港口和仓库最近的两个收费站编号；
接下来 $n$ 行表示控制费用，第 $i$ 行包含一个整数，表示第 $i$ 个收费站的控制费用 $c$；
接下来 $m$ 行表示高速公路网，第 $j$ 行包含两个整数 $x$ 和 $y$，表示在 $x$ 和 $y$ 收费站之间有一条公路段相连。每一条高速公路段只出现一次。

输出格式

唯一的一行输出应包含最小控制集中收费站的编号，以递增顺序输出，用一个空格分隔。
如果有多于一个最小控制集，你的程序可以输出任意一个。

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

1 4

数据范围与提示

对于 $40\%$ 的测试数据，$n\le 20$；
对于全部数据，$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\le 10^7$，$1\le x<y\le n$。