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 <cstdio>
#include <vector>
#include <algorithm>
#define scanf(args...) (scanf(args) ? : 0)
typedef long long int LL;
const int MAXN = 2e5+5;
const int MAXK = 5e5+5;

using std::vector;
using std::pair;
using std::make_pair;

int n, m, k, p[MAXN], size[MAXN];
pair<int, int> move[MAXN];
pair<int, int> query[MAXK];
int queryId[MAXK], data;
bool usedQuery[MAXK];
LL result;

struct Fiolka {
    vector<int> set;
    vector<pair<int, int>> counterSet;

    void fix() {
        std::vector<pair<int, int>> vec;
        for (pair<int, int> p: counterSet)
            if (!usedQuery[p.second])
                vec.push_back(p);

        counterSet = vec;
    }
} fiolka[MAXN];

int find(int u) {
    if (p[u] == u)
        return u;
    return p[u] = find(p[u]);
}

void connect(int u, int v) {
    p[find(v)] = find(u);
}

template<class T> void mergeVectors(std::vector<T>& dest, const std::vector<T>& src) {
    std::vector<T> res(dest.size()+src.size());
    std::merge(dest.begin(), dest.end(), src.begin(), src.end(), res.begin());
    dest = res;
}

void merge(int largerId, int smallerId) {
    connect(largerId, smallerId);
    
    Fiolka& larger = fiolka[largerId];
    Fiolka& smaller = fiolka[smallerId];
    
    int queryIdSize = 0;
    auto& counterSet = larger.counterSet;
    for (int p: smaller.set) {
        auto it = std::lower_bound(counterSet.begin(), counterSet.end(), make_pair(p, 0));
        while (it != counterSet.end() && it->first == p) {
            usedQuery[it->second] = true;
            queryId[queryIdSize++] = it->second;
            it++;
        }
    }

    std::sort(queryId, queryId+queryIdSize);
    for (int i=0; i<queryIdSize; i++) {
        int a = query[queryId[i]].first, b = query[queryId[i]].second;
        int s = std::min(size[a], size[b]);
        result += 2*s;

        size[a] -= s;
        size[b] -= s;
    }

    mergeVectors(larger.set, smaller.set);
    mergeVectors(larger.counterSet, smaller.counterSet);

    vector<int>().swap(smaller.set);
    vector<pair<int, int>>().swap(smaller.counterSet);

    larger.fix();
}

int main() {
    scanf("%d%d%d", &n, &m, &k);

    for (int i=0; i<n; i++)
        p[i] = i;

    for (int i=0; i<n; i++)
        scanf("%d", &size[i]);
    for (int i=0; i<m; i++) {
        scanf("%d%d", &move[i].first, &move[i].second);
        move[i].first--;
        move[i].second--;
    }

    for (int i=0; i<k; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        a--, b--;
        
        query[i] = { a, b };
        fiolka[a].counterSet.push_back({ b, i });
        fiolka[b].counterSet.push_back({ a, i });
    }

    for (int i=0; i<n; i++) {
        fiolka[i].set = { i };
        std::sort(fiolka[i].counterSet.begin(), fiolka[i].counterSet.end());
    }
    
    for (int i=0; i<m; i++) {
        int a = move[i].first, b = move[i].second;
        if (fiolka[find(a)].set.size() > fiolka[find(b)].set.size())
            merge(find(a), find(b));
        else
            merge(find(b), find(a));
    }
    
    printf("%Ld\n", result);
}