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<iostream>
#include<vector>
#include<set>
#include<list>
#include<queue>

using namespace std;

struct tOsady {
  long i, b;
  list<tOsady>::iterator itb;
  tOsady(long _i, long _b) : i(_i), b(_b) {};
  tOsady(long _i, long _b, list<tOsady>::iterator _itb) : i(_i), b(_b), itb(_itb) {};
};

struct tNaHeap {
  long i, a, b;
  tNaHeap(long _i, long _a, long _b) : i(_i), a(_a), b(_b) {};
  bool operator<(const tNaHeap &rhs) const {
    return i > rhs.i;
  }
};

int main() {
  ios_base::sync_with_stdio(0);

  long n, m, k;
  long a, b;
  long long wynik = 0;
  cin >> n >> m >> k;
  vector<set<long> >  fiolki(n);
  vector<long> ilosci(n);
  vector<long> iloscosadow(n, 0);
  vector<pair<long, long> > kroki(m);
  vector<list<tOsady> > osady(n);
  priority_queue<tNaHeap> sterta;

  for(long i = 0; i < n; ++i) {
    cin >> ilosci[i];
  }
  for(long i = 0; i < m; ++i) {
    cin >> a >> b;
    kroki[i] = make_pair(a - 1, b - 1);
  }
  list<tOsady>::iterator itosady;
  for(long i = 0; i < k; i++) {
    cin >> a >> b;
    osady[a - 1].push_back(tOsady(i, b - 1));
    itosady = --osady[a - 1].end();
    osady[b - 1].push_back(tOsady(i, a - 1, itosady));
    itosady->itb = --osady[b - 1].end();
    ++iloscosadow[a - 1];
    ++iloscosadow[b - 1];
  }
  for(long i = 0; i < n; ++i)
    if(iloscosadow[i])
      fiolki[i].insert(i);

  set<long>* f1;
  set<long>* f2;
  set<long>::iterator ff;

  for(vector<pair<long, long> >::iterator ikr = kroki.begin();
      ikr != kroki.end(); ++ikr) {
    if(iloscosadow[ikr->first] > iloscosadow[ikr->second]) {
      f1 = &fiolki[ikr->second];
      f2 = &fiolki[ikr->first];
    } else {
      f1 = &fiolki[ikr->first];
      f2 = &fiolki[ikr->second];
    }
    for(set<long>::iterator its = f1->begin(); its != f1->end(); ++its)
      for(list<tOsady>::iterator ito = osady[*its].begin();
          ito != osady[*its].end(); ++ito)
        if(f2->find(ito->b) != f2->end())
          sterta.push(tNaHeap(ito->i, ito->b, *its));
    for(set<long>::iterator its = fiolki[ikr->first].begin();
        its != fiolki[ikr->first].end(); ++its)
      fiolki[ikr->second].insert(*its);
    fiolki[ikr->first].clear();
    iloscosadow[ikr->second] += iloscosadow[ikr->first];
    iloscosadow[ikr->first] = 0;
    while(!sterta.empty()) {
      if(ilosci[sterta.top().a] > ilosci[sterta.top().b]) {
        wynik += ilosci[sterta.top().b];
        ilosci[sterta.top().a] -= ilosci[sterta.top().b];
        ilosci[sterta.top().b] = 0;
      } else {
        wynik += ilosci[sterta.top().a];
        ilosci[sterta.top().b] -= ilosci[sterta.top().a];
        ilosci[sterta.top().a] = 0;
      }
      if(!ilosci[sterta.top().a]) {
        ff = fiolki[ikr->second].find(sterta.top().a);
        if(ff != fiolki[ikr->second].end()) {
          fiolki[ikr->second].erase(ff);
          for(list<tOsady>::iterator ito = osady[sterta.top().a].begin();
              ito != osady[sterta.top().a].end(); ++ito)
            osady[ito->b].erase(ito->itb);
          iloscosadow[ikr->second] -= osady[sterta.top().a].size();
          osady[sterta.top().a].clear();
        }
      }
      if(!ilosci[sterta.top().b]) {
        ff = fiolki[ikr->second].find(sterta.top().b);
        if(ff != fiolki[ikr->second].end()) {
          fiolki[ikr->second].erase(ff);
          for(list<tOsady>::iterator ito = osady[sterta.top().b].begin();
              ito != osady[sterta.top().b].end(); ++ito)
            osady[ito->b].erase(ito->itb);
          iloscosadow[ikr->second] -= osady[sterta.top().b].size();
          osady[sterta.top().b].clear();
        }
      }
      sterta.pop();
    }
  }
  cout << wynik * 2;
  return 0;
}