BOJ. ACM Craft (1005)

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		int test = toi(br.readLine());
		int[] cost;
		int[] line;
		Node[] nodes;

		for(int iter = 0; iter < test; iter++) {
			line = getArr();
			int n = line[0], k = line[1];
			cost = getArr();
			nodes = new Node[n];

			for(int i = 0; i < n; i++) nodes[i] = new Node(i, cost[i]);

			for(int i = 0; i < k; i++) {
				line = getArr();
				int a = line[0] - 1, b = line[1] - 1;
				nodes[b].deg++;
				nodes[a].list.add(nodes[b]);
			}

			int haveToBuild = toi(br.readLine()) - 1;

			Queue<Node> q = new LinkedList<>();
			int min = Integer.MAX_VALUE;

			for(int i = 0; i < n; i++) {
				if(nodes[i].init || nodes[i].deg != 0) continue;
				q.add(nodes[i]);

				while(!q.isEmpty()) {
					Node node = q.poll();

					for(Node next: node.list) {
						if(next.init) {
							next.min = Math.max(next.min, node.min + cost[next.idx]);
							if(--next.deg == 0) q.add(next);
						} else {
							next.min = node.min + cost[next.idx];
							if(--next.deg == 0) q.add(next);
							next.init = true;
						}
					}
				}
			}
			sb.append(nodes[haveToBuild].min).append("\n");
		}
		print(sb);
	}

	static class Node {
		ArrayList<Node> list = new ArrayList<>();
		int deg;
		int min;
		int idx;
		boolean init;

		Node(int idx, int min) { this.idx = idx; this.min = min; }
	}

	static int toi(String s) { return Integer.parseInt(s); }
	static String[] getLine() throws IOException { return br.readLine().split(" "); }
	static int[] getArr() throws IOException { return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); }
	static <T> void print(T s) { System.out.print(s); }
	static <T> void println(T s) { System.out.println(s); }
}