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
125
126
127
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <map>

using namespace std;

const int MAX_N=200001;
const int MAX_K=500001;

int v[MAX_N];
int ptr[MAX_N];
int size[MAX_N];
int Time[MAX_N];

int T;

struct triple {
  int a,b,id1,id2;
  
  bool operator < (const triple &t) const {
    if(id1!=t.id1) return id1<t.id1;
    return id2<t.id2;
  }
  
};

triple triples[MAX_K];

long long res = 0;

int Find(int a) {
  if(ptr[a] == a) return a;
  return Find(ptr[a]);
}
 
int Find2(int a) {
  if(ptr[a]==a) return a;
  
  int fa = Find2(ptr[a]);
  ptr[a] = fa;
  
  return fa;
}

bool Union(int a, int b) {
  int fa = Find(a);
  int fb = Find(b);
 
  if(fa == fb) return false;
  
  if(size[fa] <= size[fb]) {
    size[fb] += size[fa];
    ptr[fa] = fb;
    Time[fa]=(++T);
  } else {
    size[fa] += size[fb];
    ptr[fb] = fa;
    Time[fb]=(++T);
  }
  
  return true;
}

int main(int argc, char *argv[]) {  
  int n,m,k,a,b;
  
  scanf("%d%d%d", &n,&m,&k);
 
  for(int i=1; i<=n; i++) {
    scanf("%d", &a);
    size[i]=1;
    ptr[i]=i;
    v[i]=a;
  }
  
  for(int i=1; i<=m; i++) {
    scanf("%d%d", &a, &b);
    Union(a,b);
  }
  
  for(int i=1; i<=k; i++) {
    scanf("%d%d", &a, &b);
    triples[i].a=a; triples[i].b=b; triples[i].id2=i;
    if(Find(a) == Find(b)) { 
      map<int,int> mp;
      int id1;
       
      int x=(size[a]<size[b]) ? a : b;
      while(x!=ptr[x]) {
        mp[ptr[x]]=Time[x];
        x=ptr[x];
      }
      
      int y=(size[a]<size[b]) ? b : a;
      if(mp.find(y)!=mp.end()) id1=mp[y];
      else {
        while(y!=ptr[y]) {
          id1=Time[y];
          y=ptr[y];
          if(mp.find(y)!=mp.end()) {
            id1=max(id1, mp[y]);
            break;
          }
        }
      }

      triples[i].id1=id1;
    }
    else triples[i].id1=1000000;
  }
  
  sort(triples+1, triples+1+k);

  for(int i=1; i<=k; i++) {
    a=triples[i].a; b=triples[i].b;
    if(Find2(a) == Find2(b)) {
      int d = min(v[a], v[b]);
      res += 2*d;
      v[a] -= d;
      v[b] -= d;
    }
  }

  printf("%lld\n", res);
  return 0;
}