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
114
115
116
117
118
119
120
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<list>

typedef long long int64;

using namespace std;

typedef struct {
	int quan;
	vector<pair<int, int> > his;
} sub_t;

typedef struct {
	list<int>* subs;
	int size;
} fio_t;

typedef struct {
	int s1, s2, time, prio;
} rea_t;

bool reas_cmp(const rea_t& r1, const rea_t& r2) {
	if (r2.time > r1.time) return true;
	if (r2.time < r1.time) return false;
	if (r2.prio > r1.prio) return true;
	return false;
}

int main () {
	int n, m, k, i, from, to, join_from, join_to, tmp, fake_to, li1, li2, last_common, l, ri, mid, amount;
	scanf("%d %d %d", &n, &m, &k);
	vector<sub_t> subs;
	subs.reserve(n + 3);
	vector<fio_t> fios;
	fios.reserve(n + 3);
	list<int>::iterator it;
	vector<pair<int, int> >* h1;
	vector<pair<int, int> >* h2;
	for (i = 0; i < n; ++i) {
		sub_t s;
		scanf("%d", &s.quan);
		s.his.push_back(make_pair(i, -1));
		subs.push_back(s);
		fio_t f;
		f.subs = new list<int>();
		f.subs->push_front(i);
		f.size = 1;
		fios.push_back(f);
	}
	for (i = 0; i < m; ++i) {
		scanf("%d %d", &from, &to);
		--from;
		--to;
		join_from = from;
		join_to = to;
		if (fios[join_from].size > fios[join_to].size) {
			tmp = join_from;
			join_from = join_to;
			join_to = tmp;
		}
		fios[to].size += fios[from].size;
		fios[from].size = 0;
		fake_to = subs[*(fios[join_to].subs->begin())].his[subs[*(fios[join_to].subs->begin())].his.size() - 1].first;
		for (it = fios[join_from].subs->begin(); it != fios[join_from].subs->end(); it++) {
			subs[*it].his.push_back(make_pair(fake_to, i));
		}
		fios[join_to].subs->splice(fios[join_to].subs->begin(), *(fios[join_from].subs));
		fios[to].subs = fios[join_to].subs;
	}
	fios.clear();
	vector<rea_t> reas;
	for (i = 0; i < k; ++i) {
		rea_t r;
		scanf("%d %d", &r.s1, &r.s2);
		--r.s1;
		--r.s2;
		r.prio = i;
		h1 = &(subs[r.s1].his);
		h2 = &(subs[r.s2].his);
		li1 = h1->size() - 1;
		li2 = h2->size() - 1;
		if ((*h1)[li1].first != (*h2)[li2].first) {
			continue;
		}
		last_common = -1;
		if ((*h1)[li1] == (*h2)[li2]) {
			l = 0;
			ri = min(li1, li2);
			while (ri - l >= 2) {
				mid = (ri + l) / 2;
				if ((*h1)[li1 - mid] == (*h2)[li2 - mid]) {
					l = mid;
					continue;
				}
				ri = mid - 1;
			}
			last_common = (*h1)[li1 - ri] == (*h2)[li2 - ri] ? ri : l;
		}
		r.time = max((*h1)[li1 - last_common - 1].second, (*h2)[li2 - last_common - 1].second);
		reas.push_back(r);
	}
	sort(reas.begin(), reas.end(), reas_cmp);
	int64 result = 0;
	for (i = 0; i < reas.size(); ++i) {
		amount = min(subs[reas[i].s1].quan, subs[reas[i].s2].quan);
		if (amount == 0) {
			continue;
		}
		subs[reas[i].s1].quan -= amount;
		subs[reas[i].s2].quan -= amount;
		result += amount;
	}
	printf("%lld\n", 2 * result);
	return 0;
}