N = int(input())
for _ in range(N):
n, m, k = map(int, input().split())
h = list(map(int, input().split()))
d = [list(map(int, input().split())) for _ in range(m)]
dep = {}
for i in d:
if i[1] - 1 not in dep:
dep[i[1] - 1] = []
dep[i[1] - 1].append(i[0] - 1)
es = [0] * n ee = [0] * n nd = [0] * n
for i in range(n):
if i in dep:
mes = 0 mnd = -1 for dd in dep[i]:
nnd = nd[dd] + int(h[dd] > h[i])
if nnd > mnd:
mnd = nnd
mes = es[dd]
elif nnd == mnd:
mes = min(mes, es[dd])
es[i] = mes
ee[i] = h[i]
nd[i] = mnd
else:
es[i] = h[i]
ee[i] = h[i]
nd[i] = 0
tee = [k * nd[i] + ee[i] for i in range(len(ee))]
os = sorted(range(len(es)), key=es.__getitem__)
oe = sorted(range(len(tee)), key=tee.__getitem__)
time = max(tee) - min(es)
seen = set()
pmee = max(tee)
nnes = min(es)
nnis = 0
for i in range(len(es) - 1):
seen.add(oe[i])
while os[nnis] in seen:
nnis += 1
nnes = es[os[nnis]]
time = min(time, max(pmee, k + tee[oe[i]]) - nnes)
print(time)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl "\n"
typedef vector<ll> vll;
#define pb push_back
#define fori(n) for (ll i=0; i<n; i++)
#define forj(n) for (ll j=0; j<n; j++)
#define fork(n) for (ll k=0; k<n; k++)
#define forn(n) for (ll i=1; i<=n; i++)
#define forn2(n) for (ll j=1; j<=n; j++)
#define forn3(n) for (ll k=1; k<=n; k++)
#define Sort(a) sort(a.begin(),a.end())
const int N=2e5+5;
vll g[N];
vll p;
ll k;
vll vis(N),a(N),vis2(N);
vll ans(N);
void dfs(ll v){
vis[v]=true;
for(auto c:g[v]){
if(vis[c]){
// if(minn[c])
continue;
}
dfs(c);
}
p.pb(v);
}
ll mini=1e14,maxi=0;
void dfs2(ll v){
vis2[v]=true;
for(auto c:g[v]){
if(vis2[c]){
if(a[c]<a[v])
{
ans[v]=max(ans[v],ans[c]+k);
}
else ans[v]=max(ans[v],ans[c]);
continue;
}
dfs2(c);
if(a[c]<a[v])
{
ans[v]=max(ans[v],ans[c]+k);
}
else ans[v]=max(ans[v],ans[c]);
}
// maxi=max(maxi,ans[v]);
}
void solve(){
ll n,m;
cin>>n>>m>>k;
vll b;
mini=1e14;maxi=0;
forn(n)
{
cin>>a[i];
b.pb(a[i]);
ans[i]=a[i];
}
fori(m)
{
ll x,y;
cin>>x>>y;
g[x].pb(y);
}
forn(n)
{
if(!vis[i])dfs(i);
}
reverse(p.begin(),p.end());
vector<pair<ll, ll>> ve;
// fori(p.size())
// {
// if(!vis2[p[i]]){
// dfs2(p[i]);
// mini=a[p[i]];
// maxi=ans[p[i]];
// ve.pb({mini,maxi});
// }
// }
forn(n)
{
if(!vis2[i]){
dfs2(i);
mini=a[i];
maxi=ans[i];
ve.pb({mini,maxi});
}
}
// Sort(b);
Sort(ve);
priority_queue<ll> pq;
multiset<ll> st;
fori(ve.size())st.insert(ve[i].second);
ll ves=ve.size();
fori(ves)
{
ve.pb({ve[i].first+k,ve[i].second+k});
}
ll anss=1e14;
fori(ves)
{
auto po=*(--st.end());
anss=min(anss,po-ve[i].first);
st.erase(st.find(ve[i].second));
st.insert(ve[i].second+k);
}
cout<<anss<<endl;
fori(n+3)
{
ans[i]=0;
g[i].clear();
vis[i]=0;
vis2[i]=0;
}
p.clear();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//Redeem yourself King.
ll n;
cin>>n;
while(n--)solve();
return 0;
}
729D - Sea Battle | 788A - Functions again |
1245B - Restricted RPS | 1490D - Permutation Transformation |
1087B - Div Times Mod | 1213B - Bad Prices |
1726B - Mainak and Interesting Sequence | 1726D - Edge Split |
1726C - Jatayu's Balanced Bracket Sequence | 1726A - Mainak and Array |
1613C - Poisoned Dagger | 475B - Strongly Connected City |
652B - z-sort | 124B - Permutations |
1496C - Diamond Miner | 680B - Bear and Finding Criminals |
1036E - Covered Points | 1015D - Walking Between Houses |
155B - Combination | 1531A - Зингер | color |
1678A - Tokitsukaze and All Zero Sequence | 896A - Nephren gives a riddle |
761A - Dasha and Stairs | 1728B - Best Permutation |
1728A - Colored Balls Revisited | 276B - Little Girl and Game |
1181A - Chunga-Changa | 1728C - Digital Logarithm |
1728D - Letter Picking | 792B - Counting-out Rhyme |