4379: 「BalticOI 2008」黑手党

**题目译自 [BalticOI 2008](http://b08.oi.edu.pl/downloads/booklet.pdf) Day0「[Mafia](https://main.edu.pl/en/archive/boi/2008/maf)」** 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