1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <vector>
#include <algorithm>
//~ #define E(arg...) fprintf(stderr, arg)
#define E(arg...)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) (int)(x).size()
#define VAR(v,n) __typeof(n) v=n
#define FOREACH(i,c) for(VAR(i,(c).begin()); i!=(c).end(); ++i)
#define PB push_back
#define MP make_pair
#define ST first
#define ND second
#define P(x) (1<<(x))
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<PII, PII> PPI;

const int N = 2e5;
const int L = 20;

int n, m, k, am[N+1], to[L][N+1], d[N+1], pre[N+1];
vector<int> v[N+1];
vector<PPI> t[N+1];
LL r;

void ddfs(int x)
{
	static int at = 0;
	pre[x] = ++at;
	FOREACH(i, v[x]) d[*i] = d[x]+1, ddfs(*i);
}

void adfs(int x)
{
	FOREACH(i, v[x]) adfs(*i);
	
	sort(ALL(t[x]));
	//~ E("adfs(%d)\n", x);
	//~ FOREACH(i, t[x]) E("(%d, %d), (%d, %d)\n", i->ST.ST, i->ST.ND, i->ND.ST, i->ND.ND);
	FOREACH(i, t[x]) {
		int s = min(am[i->ND.ST], am[i->ND.ND]);
		am[i->ND.ST] -= s;
		am[i->ND.ND] -= s;
		r += 2*s;
	}
}


int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i=1; i<=n; ++i) scanf("%d", &am[i]);
	for (int i=0, a, b; i<m; ++i) {
		scanf("%d%d", &a, &b);
		to[0][a] = b;
		v[b].PB(a);
	}
	
	for (int i=1; i<=n; ++i) if (to[0][i] == 0) ddfs(i);
	for (int i=1; i<L; ++i) for (int j=1; j<=n; ++j)
		to[i][j] = to[i-1][to[i-1][j]];
	
	for (int i=0, a, b; i<k; ++i) {
		scanf("%d%d", &a, &b);
		if (d[a] < d[b]) swap(a, b);
		
		int x = a, y = b;
		for (int j=L-1; j>=0; --j)
			if (d[x]-P(j) >= d[y]+1) x = to[j][x];
		//~ E("just before lca: %d %d\n", x, y);
		if (to[0][x] == y) t[y].PB(MP(MP(pre[x], i), MP(a, b)));
		else {
			if (d[x] != d[y]) x = to[0][x];
			
			for (int j=L-1; j>=0; --j) if (to[j][x] != to[j][y]) {
				x = to[j][x];
				y = to[j][y];
			}
			
			PII priority = MP(max(pre[x], pre[y]), i);
			t[to[0][x]].PB(MP(priority, MP(a, b)));
		}
	}
	
	for (int i=1; i<=n; ++i) if (to[0][i] == 0) adfs(i);
	
	printf("%lld\n", r);
	return 0;
}