Ta chia ~m~ đề xuất thành các block độ dài ~K = \sqrt M~.

Ta có vector truy vấn dưới dạng: vector<int> Q[N/K][N/K]

Nếu truy vấn có ~r-l+1 \le 2 \times K~, ta duyệt qua các cạnh và sử dụng ~DFS/BFS~ để tính thành phần liên thông có tổng lớn nhất.

Ngược lại, gọi ~X~ là chỉ số của block chứa ~l~, ~Y~ là chỉ số của block chứa ~r~, ta lưu truy vấn này vào ~Q[X+1][Y-1]~ để tra lời truy vấn sau.

Sau khi hoàn tất quá trình trên, ta sẽ xử lí các truy vấn chưa được tính. Ta sẽ duyệt như sau:

for (Y : N/K --> 1)
    Khởi tạo lại DSU
    for (X : Y --> 1)
        Thêm các cạnh của X vào DSU.
        Trả lời các truy vấn có trong Q[X][Y].
        Các truy vấn trên có tối đa 2*K cạnh chưa xét, lúc này xử lí như trường hợp đầu tiên.

#include <bits/stdc++.h>
#define BIT(x, i) (((x)>>(i))&1)
#define MASK(i) (1LL<<(i))
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define discrete(x) x.resize(unique(all(x)) - x.begin())
#define mp make_pair
#define pb push_back
#define TASK "test"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vll;
typedef vector<pll> vlll;

template<typename T1, typename T2> bool mini(T1 &a, T2 b) {if(a>b) a=b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b) {if(a<b) a=b; else return 0; return 1;}
template<typename T1> T1 abs(T1 a) {if(a<0) a*=-1; return a;}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll h){return l + ll(rd()) * rd() %(h-l+1);}

const int BL = 470;
int blockIDof(int i) {return i/BL;}
pair<int, int> idsOfBlock(int i) {return {i*BL, (i+1)*BL-1};}

class DSU
{
public:
    DSU(int n, vector<int> a)
    : n(n)
    , a(a)
    , par(n, -1)
    , w(a)
    , ans(a[max_element(all(a)) - a.begin()])
    , st()
    {
        reset();
    }

    void reset() {
        while(!st.empty()) rollback();
    }

    int getAns() {
        return ans;
    }

    void join(int u, int v) {
        u = root(u);
        v = root(v);
        State state = {u, v, par[u], par[v], w[u], w[v], ans};
        st.push_back(state);
        if(u == v) return;
        if(par[u] > par[v]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
        w[u] += w[v];
        w[v] = 0;
        maxi(ans, w[u]);
    }

    void rollback() {
        State state = st.back(); st.pop_back();
        par[state.u] = state.parU;
        par[state.v] = state.parV;
        w[state.u] = state.wU;
        w[state.v] = state.wV;
        ans = state.ans;
    }

private:
    int root(int u) {
        return par[u] < 0 ? u : root(par[u]);
    }

private:
    struct State
    {
        int u, v, parU, parV, wU, wV, ans;
    };

public:
    int n;
    vector<int> a, par, w;
    int ans;
    vector<State> st;
};

int n, m, q;
vector<int> a, x, y, l, r, ans;

int solveEdgeCase(DSU &dsu, int l, int r) {
    for(int i = l; i <= r; ++i)
        dsu.join(x[i], y[i]);
    auto ans = dsu.getAns();
    dsu.reset();
    return ans;
}

int solveCompressedCase(DSU &dsu, int l, int r) {
    int L = idsOfBlock(blockIDof(l)+1).fi;
    int R = idsOfBlock(blockIDof(r)-1).se;
    assert(L <= R);
    assert(l <= L && R <= r);

    for(int i = l; i < L; ++i)
        dsu.join(x[i], y[i]);
    for(int i = R + 1; i <= r; ++i)
        dsu.join(x[i], y[i]);

    int ans = dsu.getAns();

    for(int i = l; i < L; ++i)
        dsu.rollback();
    for(int i = R + 1; i <= r; ++i)
        dsu.rollback();

    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    // Input
    cin >> n >> m >> q;
    a.resize(n);
    x.resize(m);
    y.resize(m);
    l.resize(q);
    r.resize(q);
    ans.resize(q, -1);
    for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 0; i < m; ++i) cin >> x[i] >> y[i], --x[i], --y[i];
    for(int i = 0; i < q; ++i) cin >> l[i] >> r[i], --l[i], --r[i];

    // Solve
    DSU dsu(n, a);

    vector<vector<vector<int>>> Query(blockIDof(m-1) + 1, vector<vector<int>>(blockIDof(m-1) + 1, vector<int>(0)));
    for(int i = 0; i < q; ++i) {
        if(blockIDof(l[i]) + 1 <= blockIDof(r[i]) - 1)
            Query[blockIDof(l[i]) + 1][blockIDof(r[i]) - 1].pb(i);
        else ans[i] = solveEdgeCase(dsu, l[i], r[i]);
    }

    for(int i = 0; i < Query.size(); ++i) {
        dsu.reset();
        for(int j = i; j < Query.size(); ++j) {
            for(int k = idsOfBlock(j).fi; k <= idsOfBlock(j).se && k < m; ++k) {
                dsu.join(x[k], y[k]);
            }
            assert(i < Query.size() && j < Query[i].size());
            for(int id : Query[i][j])
                ans[id] = solveCompressedCase(dsu, l[id], r[id]);
        }
    }

    // Output
    for(int i = 0; i < q; ++i) assert(ans[i] != -1);
    for(int i = 0; i < q; ++i) cout << ans[i] << '\n';

    return 0;
}