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
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
using namespace std;
typedef pair<int,int> PI;
typedef long long LL;
typedef double D;
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define R(I,N) for(int I=0;I<N;I++)
#define F(I,A,B) for(int I=A;I<B;I++)
#define FD(I,N) for(int I=N-1;I>=0;I--)
#define VAR(v,i) __typeof(i) v=(i)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i)
#define make(A) scanf("%d",&A)
#define MAXn 200100
#define MAXk 500100
int a[MAXk],b[MAXk];
vector<int> re[MAXn];
int n,m,k,g[MAXn],ak[MAXn];
int f[MAXn];
LL wyn;

//algorytm Tarjana, z biblioteczki Marka Cygana
const int N=501000;
vector<int> kraw[N],pytania[N];
int kolor[N],fu[N],przodek[N];

int fufind(int x){ return fu[x]<0?x:fu[x]=fufind(fu[x]); }

 //wywolujemy DfsTarjan(wierzcholek,-1);
 //zapytania umieszczamy w zmiennej pytania;
 //zakladam, ze pytamy o 2 rozne wierzcholki
void DfsTarjan(int x,int parent){
	kolor[x]=1; fu[x]=-1; przodek[x]=x;
	FOREACH(it,kraw[x]) if (*it!=parent){
		DfsTarjan(*it,x);
		int a=fufind(x),b=fufind(*it);
		if (fu[a]<fu[b]) swap(a,b);
		fu[b]+=fu[a]; fu[a]=b;
		przodek[b]=x;
	}
	FOREACH(it,pytania[x]){
		int ak = a[*it] + b[*it] - x;
		if (kolor[ak]==2)
			re[przodek[fufind(ak)]-n].PB(*it);
	}
	kolor[x]=2;
}
inline void dodaj_krawedz(int a,int b){
	kraw[a].PB(b);
	kraw[b].PB(a);
}
inline void dodaj_pytanie(int a,int b,int i){
	pytania[a].PB(i);
	pytania[b].PB(i);
}
//-----------------------------

int find(int a){
	return f[a]==a?a:f[a]=find(f[a]);
}
void uni(int a,int b){
	f[find(a)]=find(b);
}

int it;
inline void wlej(int a,int b){
	a = find(a);
	b = find(b);
	dodaj_krawedz(ak[a],it);
	dodaj_krawedz(ak[b],it);
	uni(a,b);
	ak[b] = it;
	ak[a] = it;
	it++;
}
main(){
	make(n);make(m);make(k);
	R(i,n){
		make(g[i]);
		ak[i] = i;
		f[i] = i;
	}
	it = n;
	R(i,m){
		int a,b;make(a);make(b);a--;b--;
		wlej(a,b);
	}
	R(i,n)if(find(1) != find(i))wlej(1,i);
	R(i,k){
		make(a[i]);
		make(b[i]);
		a[i]--;
		b[i]--;
		dodaj_pytanie(a[i],b[i],i);
	}
	DfsTarjan(2*n-2,-1);
	R(i,m){
		sort(re[i].begin(),re[i].end());
		R(j,re[i].size()){
			int pom = re[i][j];
			int ile = min(g[a[pom]],g[b[pom]]);
			wyn += 2*ile;
			g[a[pom]] -= ile;
			g[b[pom]] -= ile;
		}
	}
	printf("%lld\n",wyn);
}