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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

typedef long long int ll;

const int infty = 1e9;

ll wynik = 0LL;

int n, m, k;

vector<pair<int, int> > graf[200005];
int tim[200005];
vector<pair<int, int> > zap[200005];
vector<pair<int, int> > rea[200005];

pair<int, int> par[500005];

int ile[200005];

inline void reaguj(int a, int b)
{
	const int heh = min(ile[a], ile[b]);
	wynik += heh;
	ile[a] -= heh;
	ile[b] -= heh;
}

bool uz[500005];

int odp[500005];
int piesek[500005];

int fut[200005];
int fuf(int w) { return (fut[w] == w) ? w : (fut[w] = fuf(fut[w])); }
inline void fuu(int u, int v) { fut[fuf(u)] = fuf(v); }

bool comp(const pair<int, int> &a, const pair<int, int> &b)
{
	return a.second < b.second;
}

void podlicz(int w)
{
	for(int i = 0; i < graf[w].size(); i++)
		podlicz(graf[w][i].first);
	stable_sort(rea[w].begin(), rea[w].end(), comp);
	for(int i = 0; i < rea[w].size(); i++)
		reaguj(par[rea[w][i].first].first, par[rea[w][i].first].second);
}

void licz_lca(int w)
{
	for(int i = 0; i < zap[w].size(); i++)
	{
		if(uz[zap[w][i].second])
		{
			odp[zap[w][i].second] = fuf(zap[w][i].first);
			piesek[zap[w][i].second] = tim[odp[zap[w][i].second]];
		}
		else
			uz[zap[w][i].second] = true;
	}
	for(int i = 0; i < graf[w].size(); i++)
	{
		tim[w] = graf[w][i].second;
		licz_lca(graf[w][i].first);
		fuu(graf[w][i].first, w);
	}
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= n; i++)
		scanf("%d", ile + i);
	for(int i = 1; i <= m; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		graf[b].push_back(make_pair(a, i));
		uz[a] = true;
	}
	for(int i = 1; i <= n; i++)
	{
		fut[i] = i;
		if(uz[i])
			uz[i] = false;
		else
			graf[0].push_back(make_pair(i, infty));
	}
	for(int i = 1; i <= k; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		zap[a].push_back(make_pair(b, i));
		zap[b].push_back(make_pair(a, i));
		par[i] = make_pair(a, b);
	}
	licz_lca(0);
	for(int i = 1; i <= k; i++)
	{
		rea[odp[i]].push_back(make_pair(i, piesek[i]));
	}
	for(int i = 0; i < graf[0].size(); i++)
		podlicz(graf[0][i].first);
	printf("%lld\n", wynik * 2);
	return 0;
}