#ifdef __LOCAL #define _GLIBCXX_DEBUG #endif #include using namespace std; using ll = long long; using P = pair; using PIL = pair; using PLI = pair; using PLL = pair; template bool chmin(T &a, T b) {if(a>b){a=b;return 1;}return 0;} template bool chmax(T &a, T b) {if(a void show_vec(T v) {for (int i=0;i void show_pair(T p) {cout< bool judge_digit(T bit,T i) {return (((bit&(1LL< h_idx4 = {-1, 0,0,1}; const vector w_idx4 = { 0,-1,1,0}; const vector h_idx8 = {-1,-1,-1, 0,0, 1,1,1}; const vector w_idx8 = {-1, 0, 1,-1,1,-1,0,1}; struct edge { int to; ll cost; edge() = default; edge(int _to,ll _cost) : to(_to), cost(_cost) {} // 不等号を定義 bool operator<(const edge &other) const { return cost < other.cost; } bool operator>(const edge &other) const { return cost > other.cost; } }; struct Edge { int from; int to; ll cost; Edge() = default; Edge(int _from, int _to,ll _cost) : from(_from), to(_to), cost(_cost) {} // 不等号を定義 bool operator<(const Edge &other) const { return cost < other.cost; } bool operator>(const Edge &other) const { return cost > other.cost; } }; struct DSU { public: DSU() : n(0) {} DSU(int _n) : n(_n), parent_or_size(_n, -1) {} int merge(int a, int b) { assert(0 <= a && a < n); assert(0 <= b && b < n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < n); assert(0 <= b && b < n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < n); return -parent_or_size[leader(a)]; } vector> groups() { vector leader_buf(n), group_size(n); for (int i = 0; i < n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } vector> result(n); for (int i = 0; i < n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < n; i++) { result[leader_buf[i]].push_back(i); } result.erase( remove_if(result.begin(), result.end(), [&](const vector& v) { return v.empty(); }), result.end()); return result; } private: int n; // root node: -1 * component size // otherwise: parent vector parent_or_size; }; struct Graph { private: vector> G; int n,m; public: vector indegree; inline const std::vector &operator[](int k) const { return G[k]; } inline std::vector &operator[](int k) { return G[k]; } int size() const { return G.size(); } void resize(const int n) { G.resize(n); } Graph() = default; Graph(int _n) : n(_n), G(_n), indegree(_n) {} Graph(int _n, int _m, bool weight, bool directed, int index) : n(_n), m(_m), G(_n), indegree(_n,0) { input(weight,directed,index); } void input(bool weight, bool directed, int index){ int _from, _to; ll _cost = 1; for (int i = 0; i < m; i++){ cin >> _from >> _to; _from -= index; _to -= index; if (weight) cin >> _cost; G[_from].push_back(edge(_to,_cost)); if (!directed) G[_to].push_back(edge(_from,_cost)); indegree[_to]++; } } // 重みなしグラフの始点からの最短距離を求める // 到達不可能点 : -1 // O(N + M) vector BFS(int start){ vector dist(n,-1); dist[start] = 0; queue que; que.push(start); while (!que.empty()){ int now = que.front(); que.pop(); for (auto &e : G[now]){ if (dist[e.to] != -1) continue; dist[e.to] = dist[now] + 1; que.push(e.to); } } return dist; } // 辺長が 0or1 のグラフをに対し単一始点最短距離を求める (01BFS) // 到達不可能点 : INF // O(N + M) vector Zero_One_BFS(int start){ vector dist(n,INF); dist[start] = 0LL; deque que; que.push_back(start); while (!que.empty()){ auto now = que.front(); que.pop_front(); for (auto &e : G[now]){ ll next_d = dist[now] + e.cost; if (chmin(dist[e.to], next_d)){ if (e.cost == 0) que.push_front(e.to); else que.push_back(e.to); } } } return dist; } // 重み付きグラフの単一始点最短距離を求める // 負辺を持たない // 到達不可能点 : INF // O((N + M)logN) vector Dijkstra(int start){ vector dist(n,INF); dist[start] = 0LL; priority_queue, greater> pq; pq.push(edge(start,0LL)); while (!pq.empty()){ auto p = pq.top(); pq.pop(); int now = p.to; if (dist[now] < p.cost) continue; for (auto &e : G[now]){ ll next_d = dist[now] + e.cost; if (chmin(dist[e.to],next_d)){ pq.push(edge(e.to, dist[e.to])); } } } return dist; } // 負辺をもつ重み付きグラフの単一始点最短距離を求める // 到達不可能点 : INF // 負閉路 : -INF // O(NM) vector Bellman_Ford(int start){ vector dist(n, INF); dist[start] = 0LL; for (int loop = 0; loop < n - 1; loop++){ for (int v = 0; v < n; v++){ if (dist[v] == INF) continue; for (auto &e : G[v]){ ll next_d = dist[v] + e.cost; chmin(dist[e.to],next_d); } } } queue que; vector chk(n,false); for (int v = 0; v < n; v++){ if (dist[v] == INF) continue; for (auto &e : G[v]){ ll next_d = dist[v] + e.cost; if (dist[e.to] > next_d && !chk[e.to]){ que.push(e.to); chk[e.to] = true; } } } while (!que.empty()){ int now = que.front(); que.pop(); for (auto &e : G[now]){ if (!chk[e.to]){ chk[e.to] = true; que.push(e.to); } } } for (int i = 0; i < n; i++) if (chk[i]) dist[i] = -INF; return dist; } // 重み付きグラフの全頂点対間最短距離を求める // 到達不可能点 : INF // O(N^3) vector> Warshall_Floyd(){ vector> dist(n, vector(n,INF)); for (int i = 0; i < n; i++) dist[i][i] = 0LL; for (int i = 0; i < n; i++){ for (auto &e : G[i]) chmin(dist[i][e.to], e.cost); } for (int k = 0; k < n; k++){ for (int i = 0; i < n; i++){ if (dist[i][k] == INF) continue; for (int j = 0; j < n; j++){ if (dist[k][j] == INF) continue; chmin(dist[i][j],dist[i][k] + dist[k][j]); } } } return dist; } // 最小全域木の辺の重みの総和 // Gが非連結 : -1 // O(MlogM) ll Kruskal(){ vector E; for (int i = 0; i < n; i++){ for (auto &e : G[i]){ E.push_back(Edge(i,e.to,e.cost)); } } sort(E.begin(), E.end()); DSU uf(n); ll res = 0; sort(E.begin(), E.end()); for (auto &e : E){ if (!uf.same(e.from,e.to)){ uf.merge(e.from,e.to); res += e.cost; } } if (uf.size(0) != n) return -1; return res; } // DGAをトポロジカルソートする // O(V+E) vector topological_sort(){ vector res; queue que; for (int i = 0; i < n; i++){ if (indegree[i] == 0){ que.push(i); } } while (!que.empty()){ int x = que.front(); que.pop(); for (auto e : G[x]){ indegree[e.to]--; if (indegree[e.to] == 0) que.push(e.to); } res.push_back(x); } return res; } }; int n,m; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15); cin >> n >> m; vector a(n); for (int i = 0; i < n; i++){ cin >> a[i]; } Graph G(n); for (int i = 0; i < m; i++){ int from,to; cin >> from >> to; from--; to--; if (a[from] < a[to]){ G[from].push_back(edge(to,1LL)); G.indegree[to]++; } if (a[to] < a[from]){ G[to].push_back(edge(from,1LL)); G.indegree[from]++; } } int k; cin >> k; vector lamps(n,false); for (int i = 0; i < k; i++){ int b; cin >> b; b--; lamps[b] = true; } vector topo = G.topological_sort(); // for (int i = 0; i < n; i++){ // cout << topo[i] << " "; // } // cout << endl; vector op; for (int i = 0; i < n; i++){ int now = topo[i]; if (lamps[now]){ op.push_back(now); lamps[now] = false; for (auto e : G[now]){ lamps[e.to] = !lamps[e.to]; } } } cout << op.size() << endl; for (auto i : op){ cout << i + 1 << endl; } }