E

#include <bits/stdc++.h>

using namespace std;

#define ll     long long
#define _test   int _TEST; cin>>_TEST; while(_TEST--)
#define pb     push_back

int main()
{
    _test
    {
        ll int n, m, k;
        cin>>n>>m>>k;

        vector<ll int> h(n);
        for(auto &e: h)
            cin>>e;

        vector<vector<ll int>> graph(n);
        vector<int> in(n);

        for(int i=0; i<m; i++)
        {
            int u, v;
            cin>>u>>v;

            u--, v--;

            graph[u].pb(v);
            in[v]++;
        }

        vector<ll int> days(n, 1);
        vector<ll int> earliest(n, 1e18);

        vector<pair<ll int, ll int>> vp;

        for(int u=0; u<n; u++)
        {
            if(earliest[u] == 1e18)
            {
                earliest[u] = h[u];
                assert(in[u] == 0);
            }

            vp.pb({earliest[u], (days[u]-1)*1ll*k+h[u]});

            for(auto v: graph[u])
            {
                if(h[v] < h[u])
                {
                    if(days[v] < 1+days[u])
                        earliest[v] = earliest[u];
                    else if(days[v] == 1+days[u])
                        earliest[v] = min(earliest[v], earliest[u]);

                    days[v] = max(days[v], 1+days[u]);
                }
                else
                {
                    if(days[v] < days[u])
                        earliest[v] = earliest[u];
                    else if(days[v] == days[u])
                        earliest[v] = min(earliest[v], earliest[u]);

                    days[v] = max(days[v], days[u]);
                }
            }
        }

        sort(vp.begin(), vp.end());

        ll int ans = 1e18, mx;
        multiset<ll int> m1, m2;
        for(auto [_, e]: vp)        m1.insert(e);

        for(auto [st, en]: vp)
        {
            mx = *m1.rbegin();
            if(m2.size())       mx = max(mx, *m2.rbegin());
            ans = min(ans, mx - st);

            m2.insert(en+k);
        }

        cout<<ans<<"\n";
    }
}