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
92
93
94
95
96
97
98
#include<bits/stdc++.h>
#define MAXN 500010
#define PB push_back
#define PII pair<int,int>
#define ND second
#define ST first
#define LL unsigned long long
using namespace std;

int n, m, k;
int tab[MAXN], cnt[MAXN], clr[MAXN], kolw[MAXN];
vector<int> v[MAXN];
vector<PII> qrs[MAXN], ans[MAXN];
PII rqs[MAXN];
bool mark[MAXN];
LL wyn;

int find(int x)
{
	return (tab[x] == x ? x : (tab[x] = find(tab[x])));
}

void __union(int x, int y)
{
	x = find(x);
	y = find(y);
	tab[y] = x;
}

void tarjan(int x, int tree)
{
	kolw[x] = 1;
	clr[x] = tree;
	for(int i = 0; i < (int)v[x].size(); i++)
	{
		tarjan(v[x][i], tree);
		kolw[x]++;
		__union(x, v[x][i]);
	}
	for(int i = 0; i < (int)qrs[x].size(); i++)
	{
		if(clr[qrs[x][i].ST] == tree)
		{
			ans[find(qrs[x][i].ST)].PB(PII(kolw[find(qrs[x][i].ST)],qrs[x][i].ND)); 
		}
	}
}

void licz(int x)
{
	for(int i = 0; i < (int)v[x].size(); i++)
	{
		licz(v[x][i]);
	}
	sort(ans[x].begin(), ans[x].end());
	for(int i = 0; i < (int)ans[x].size(); i++)
	{
		int y = min(cnt[rqs[ans[x][i].ND].ST], cnt[rqs[ans[x][i].ND].ND]);
		cnt[rqs[ans[x][i].ND].ST] -= y;
		cnt[rqs[ans[x][i].ND].ND] -= y;
		wyn += (LL)y;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++)
	{
		cin >> cnt[i];
		tab[i] = i;
	}
	for(int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		v[y].PB(x);
		mark[x] = 1;
	}
	for(int i = 0; i < k; i++)
	{
		int x, y;
		cin >> x >> y;
		qrs[x].PB(PII(y, i));
		qrs[y].PB(PII(x, i));
		rqs[i] = PII(x, y);
	}
	for(int i = 1; i <= n; i++)
	{
		if(!mark[i])
		{
			tarjan(i, i);
			licz(i);
		}
	}
	cout << 2LL*wyn << endl;
}