[BalticOI 2008] 黑手党

题目描述

Byteland 国警方收到了一条匿名举报,其中说当地黑帮老大正计划一次从港口到郊区仓库的运输。警方知道运输的时间并且知道运输需要用到国家的高速公路网。 高速公路网包含双向的高速公路段,每个路段直接连着两个不同的收费站。一个收费站可能与很多其他的收费站相连。汽车只能通过收费站进入或离开高速公路网。据所知,黑帮会距港口边最近的收费站进入高速公路,从距仓库最近的收费站离开(不会在出高速后重新进入)。特警组位于选定的收费站处。当运输车辆进入被监控的收费站时,它就会被警察抓住。 从这个角度看,最简单的办法就是在每个收费站处都安排特警班。然而,控制一个收费站需要特定的费用,每个收费站费用不同。警方想要让花费最小,所以他们需要制定一个收费站的最小控制集,这个集合满足两个条件: - 所有从港口到仓库的交通必须至少经过集合中的一个收费站 - 监控这些收费站的费用(即监控每一个收费站费用之和)最小 你可以假设使用高速公路可以从港口到仓库。 #任务 写一个程序能够: - 从标准输入中读取高速公路网,监控代价和运输的起点和终点 - 找到收费站的最小控制集 - 输出这个集合到标准输出

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

1 4

说明

**样例解释** ![0](https://i.loli.net/2018/02/19/5a8af2c2ef8d7.gif) 这张图片显示了高速公路网中收费站的编号(在左上角)和控制费用。$1$ 号和 $4$ 号收费站组成了最小控制集,总控制费用为 $5$。 **数据范围** 对于 $40\%$ 的测试数据,$n\le 20$; 对于全部数据,$1\le n\le 200,1\le m \le 2\times 10^4$​​,$1 \le a,b \le n,a≠b$,$1\le c\le 10^7$​​,$1\le x<y\le n$。