mafia.cc

#include <cmath>
#include <vector>
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

struct Edge {
  int from, to, index;
  LL cap, flow;
  Edge(int from, int to, LL cap, LL flow, int index) :
    from(from), to(to), cap(cap), flow(flow), index(index) {}
};

struct PushRelabel {
  int N;
  vector<vector<Edge> > G;
  vector<LL> excess;
  vector<int> dist, active, count;
  queue<int> Q;

  PushRelabel(int N) : N(N), G(N), excess(N), dist(N), active(N), count(2*N) {}

  void AddEdge(int from, int to, LL cap) {
    G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
    if (from == to) G[from].back().index++;
    G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));
  }

  void Enqueue(int v) { 
    if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); } 
  }

  void Push(Edge &e) {
    LL amt = min(excess[e.from], LL(e.cap - e.flow));
    if (dist[e.from] <= dist[e.to] || amt == 0) return;
    e.flow += amt;
    G[e.to][e.index].flow -= amt;
    excess[e.to] += amt;    
    excess[e.from] -= amt;
    Enqueue(e.to);
  }

  void Gap(int k) {
    for (int v = 0; v < N; v++) {
      if (dist[v] < k) continue;
      count[dist[v]]--;
      dist[v] = max(dist[v], N+1);
      count[dist[v]]++;
      Enqueue(v);
    }
  }

  void Relabel(int v) {
    count[dist[v]]--;
    dist[v] = 2*N;
    for (int i = 0; i < G[v].size(); i++) 
      if (G[v][i].cap - G[v][i].flow > 0)
        dist[v] = min(dist[v], dist[G[v][i].to] + 1);
    count[dist[v]]++;
    Enqueue(v);
  }

  void Discharge(int v) {
    for (int i = 0; excess[v] > 0 && i < G[v].size(); i++) Push(G[v][i]);
    if (excess[v] > 0) {
      if (count[dist[v]] == 1) 
        Gap(dist[v]); 
      else
        Relabel(v);
    }
  }

  LL GetMaxFlow(int s, int t) {
    count[0] = N-1;
    count[N] = 1;
    dist[s] = N;
    active[s] = active[t] = true;
    for (int i = 0; i < G[s].size(); i++) {
      excess[s] += G[s][i].cap;
      Push(G[s][i]);
    }

    while (!Q.empty()) {
      int v = Q.front();
      Q.pop();
      active[v] = false;
      Discharge(v);
    }

    LL totflow = 0;
    for (int i = 0; i < G[s].size(); i++) totflow += G[s][i].flow;
    return totflow;
  }

  bool visit[500];

  void GetReach(int s) {
    visit[s] = true;
    for (int i = 0; i < G[s].size(); i++) {
      Edge &t = G[s][i];
      if (t.cap - t.flow > 0) {
        if(not visit[t.to])
          GetReach(t.to);
      }
    }
  }

  vector<int> cut;

  void GetCut() {
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < G[i].size(); ++j) {
        Edge &t = G[i][j];
        if (visit[t.from] and not visit[t.to] && t.cap) {
          //cout << "# " << t.from << " " << t.to << ": " << t.cap << " " << t.flow << endl;
          cut.push_back(t.from);
        }
      }
    }
    /*
    for( int i = 0 ; i < N ; i += 2 )
      if( visit[i] == true && visit[i+1] == false )
        cut.push_back(i);
    */
  }
};

#define MAXN 402
const LL INF = 1LL << 60;

int main() {
  ios::sync_with_stdio(0);
  int n, m, ini, fin, u, v, w;
  cin >> n >> m >> ini >> fin;
  --ini, --fin;
  PushRelabel G(2*n);
  for (int i = 0; i < n; i++) {
    cin >> w;
    G.AddEdge(2*i, 2*i+1, w);
  }
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    --u, --v;
    G.AddEdge(2*u+1, 2*v, INF);
    G.AddEdge(2*v+1, 2*u, INF);
  }
  LL ans = G.GetMaxFlow(2*ini, 2*fin+1);
  //cout << ans << endl;
  memset(G.visit, 0, sizeof G.visit);
  G.GetReach(2*ini);
  G.GetCut();
  sort(G.cut.begin(), G.cut.end());
  cout << (G.cut[0] >> 1) + 1 ;
  for (int i = 1; i < G.cut.size(); ++i)
    cout << " " << (G.cut[i] >> 1) + 1 ;
  cout << endl;
}