마피아

어느 마피아 조직이 고속도로망을 따라 시작 톨게이트에서 도착 톨게이트로 이동하려고 한다. 고속도로망은 n개의 톨게이트와 m개의 양방향 고속도로로 이루어져 있다. 차량은 고속도로 중간에서 나가거나 들어올 수 없으며, 모든 이동은 톨게이트와 고속도로를 통해서만 이루어진다.

각 톨게이트에는 점거 비용이 있다. 시작 톨게이트와 도착 톨게이트를 제외한 몇 개의 톨게이트를 점거하여, 마피아가 점거된 톨게이트를 지나지 않고서는 시작점에서 도착점까지 갈 수 없게 하려고 한다.

총 점거 비용이 최소가 되도록 점거할 톨게이트들을 구하여라.

첫째 줄에 톨게이트의 개수 n과 고속도로의 개수 m이 주어진다. (1 <= n <= 200, 1 <= m <= 20,000) 톨게이트 번호는 1부터 n까지이다.

둘째 줄에 마피아의 시작 톨게이트 s와 도착 톨게이트 t가 주어진다. 다음 n개의 줄에는 1번부터 n번까지 각 톨게이트의 점거 비용이 한 줄에 하나씩 주어진다. 비용은 10,000,000 이하의 자연수이다.

마지막 m개의 줄에는 고속도로로 연결된 두 톨게이트 a와 b가 주어진다. 각 고속도로는 양방향으로 이동할 수 있다.

총 점거 비용이 최소가 되도록 선택한 톨게이트 번호를 오름차순으로 한 줄에 출력한다.

출력할 톨게이트가 없으면 빈 줄을 출력한다.