#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

// AtCoder
// #include <atcoder/all>
// using namespace atcoder;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...)
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b)-1, i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fls(x) (64 - __builtin_clzll(x))
#define pcnt(x) __builtin_popcountll(x)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t; cin >> t;
    rep (_, t) {
        int n; cin >> n;
        vector<int> p(n), prev(n);
        rep (i, n) {
            cin >> p[i]; --p[i];
            prev[p[i]] = i;
        }
        vector<int> res;
        int piv = 0, cnt = 0;
        while (piv < n) {
        // rep (x, 10) {
            eprintf("piv=%d cnt=%d : ", piv, cnt);
            rep (i, n) eprintf("%d ", p[i]);
            if (prev[piv] == piv) {
                eprintf("A\n");
                ++piv;
                continue;
            }
            int pivplace = prev[piv];
            if ((pivplace + 1) % 2 == cnt % 2) {
                eprintf("B\n");
                swap(p[pivplace - 1], p[pivplace]);
                swap(prev[p[pivplace - 1]], prev[p[pivplace]]);
                ++cnt;
                res.push_back(pivplace);
            } else {
                if (p[pivplace - 2] > piv) {
                    eprintf("C\n");
                    swap(p[pivplace - 2], p[pivplace - 1]);
                    swap(prev[p[pivplace - 2]], prev[p[pivplace - 1]]);
                    ++cnt;
                    res.push_back(pivplace - 1);
                } else {
                    eprintf("D\n");
                    swap(p[pivplace - 1], p[pivplace]);
                    swap(prev[p[pivplace - 1]], prev[p[pivplace]]);
                    cnt += 5;
                    res.push_back(pivplace - 1);
                    res.push_back(pivplace);
                    res.push_back(pivplace - 1);
                    res.push_back(pivplace);
                    res.push_back(pivplace - 1);
                }
            }
        }
        cout << res.size() << '\n';
        rep (i, res.size()) cout << res[i] << " \n"[i + 1 == i_len];
    }
    return 0;
}
//AnkitCode99 here....
//every ups and downs matter!

#include<bits/stdc++.h>
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr)
typedef long long int ll;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back

using namespace std;

const ll sz=(1e5+5)*2;
const ll szz=1e6+6;
const ll mod=1e9+7;

ll n,m,price[sz],maxi[sz];
vector<ll> ar[sz];
bool vis[sz];
ll ans = -1e16;

void dfs(ll node)
{
    vis[node]=1;
    
    if(maxi[node]!=-1)
    {
        return;
    }

    maxi[node]=0;
    for(auto x:ar[node])
    {
        dfs(x);
        maxi[node] = max(maxi[node],maxi[x]);
    }

    if(ar[node].size())
    {
        ans = max(ans,maxi[node]-price[node]);
    }
    maxi[node] = max(maxi[node],price[node]);
}

int main()
{
    IOS;

    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("op.txt","w",stdout);
    #endif

    clock_t startTime=clock();

    cin>>n>>m;
    rep(i,1,n+1)
    {
        cin>>price[i];
    }

    rep(i,0,m)
    {
        ll a,b;
        cin>>a>>b;
        ar[a].pb(b);
    }

    memset(maxi,-1,sizeof maxi);

    rep(i,1,n+1)
    {
        if(!vis[i])
        {
            dfs(i);
        }
    }

    cout<<ans<<endl;

    cerr << endl <<setprecision(20)<< double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< " seconds." << endl;

}//Goodbye...