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
121
122
123
124
#include<bits/stdc++.h>
#define ALL(X)      X.begin(),X.end()
#define FOR(I,A,B)  for(int (I) = (A); (I) <= (B); (I)++)
#define FORW(I,A,B) for(int (I) = (A); (I) < (B);  (I)++)
#define FORD(I,A,B) for(int (I) = (A); (I) >= (B); (I)--)
#define CLEAR(X)    memset(X,0,sizeof(X))
#define PB          push_back
#define MP          make_pair
#define X           first
#define Y           second
using namespace std;
typedef signed long long slong;
typedef long double ldouble;
const slong Infinity = 1000000100;
const ldouble Epsilon = 1e-9;
template<typename T, typename U> ostream& operator << (ostream& os, const pair<T,U>&p) {return os << "(" << p.X << "," << p.Y << ")"; }
template<typename T> ostream& operator << (ostream &os, const vector<T>& V) { os << "["; FORW(i,0,size(V)) os << V[i] << ((i==size(V)-1) ? "" : ","); return os << "]"; }
template<typename T> ostream& operator << (ostream &os, const set<T>& S) {os << "("; for(auto i: S) os << i << (i==*S.rbegin()?"":","); return os << ")"; }
template<typename T, typename U> ostream& operator << (ostream &os, const map<T, U>& M){os << "{"; for(auto i: M) os << i << (i.X==M.rbegin()->X?"":","); return os << "}"; }
template<typename T, typename F> T lbound(T p, T q, F f) { static_assert(is_integral<T>::value, "integral type required"); while(p < q) { T r = p+(q-p)/2; if(f(r)) q = r; else p = r+1; } return p; }
template<typename T, typename F> T lboundl(T p, T q, F f) { static_assert(is_floating_point<T>::value, "floating point type required"); FOR(i,1,70) { T r = (p+q)/2; if(f(r)) q = r; else p = r; } return p; }
template<typename T, typename U> bool contain(T t, U u) { return t.find(u) != t.end(); }
template<typename T> int size(T t) { return t.size(); }

int N, M, K;
const int MAXN = 500010;
int A[MAXN];
int X1[MAXN];
int X2[MAXN];
int Y1[MAXN];
int Y2[MAXN];

struct FU
{
	int *S, *R;
	map<int,int> *M;

	FU(int n)
	{
		R = new int[n+1];
		S = new int[n+1];
		M = new map<int,int>[n+1];
		FOR(i,0,n)
		{
			M[i][i] += A[i];
			S[i] = i;
			R[i] = 1;
		}
	}
	
	int Find(int a)
	{
		if(S[a] == a) return a;
		else return S[a] = Find(S[a]);
	}
	
	void Union(int a, int b)
	{
		a = Find(a);
		b = Find(b);
		if(a != b)
		{
			if(R[a] < R[b])
			{
				S[a] = b;
				R[b] += R[a];
				for(auto m: M[a]) M[b][m.X] += m.Y;
			}
			else
			{
				S[b] = a;
				R[a] += R[b];
				for(auto m: M[b]) M[a][m.X] += m.Y;
			}
		}
	}
	
	~FU()
	{
		delete[] S;
		delete[] R;
	}
};

void read_data()
{
	scanf("%d %d %d", &N, &M, &K);
	FOR(i,1,N) scanf("%d", A+i);
	FOR(i,1,M) scanf("%d %d", X1+i, X2+i);
	FOR(i,1,K) scanf("%d %d", Y1+i, Y2+i);
}

void solve()
{	
	FU F(N);
	slong result = 0;
	FOR(i,1,M)
	{
		F.Union(X1[i],X2[i]);
		map<int,int> &Q = F.M[F.Find(X1[i])];
		FOR(j,1,K) 
		{
			int a = contain(Q,Y1[j]) ? Q[Y1[j]] : 0;
			int b = contain(Q,Y2[j]) ? Q[Y2[j]] : 0;
			int t = min(a,b);
			if(min(a,b) > 0)
			{
				result += 2*t;
				Q[Y1[j]] -= t;
				Q[Y2[j]] -= t;
				if(Q[Y1[j]] == 0) Q.erase(Y1[j]);
				if(Q[Y2[j]] == 0) Q.erase(Y2[j]);
			}
		}
	}	
	printf("%lld\n", result);
}

int main() 
{
	read_data();
	solve();
	return 0;
}