#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using namespace std;
#define all(v) v.begin(), v.end()
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep_up(i, a, b) for (ll i = a; i < b; ++i)
#define rep_down(i, a, b) for (ll i = a; i > b; --i)

#define P pair<ll, ll>
#define Graph vector<vector<ll>>
#define fi first
#define se second

#define vvvvll vector<vector<vector<vector<ll>>>>
#define vvvll vector<vector<vector<ll>>>
#define vvll vector<vector<ll>>
#define vll vector<ll>

#define vvvvdo vector<vector<vector<vector<double>>>>
#define vvvdo vector<vector<vector<double>>>
#define vvdo vector<vector<double>>
#define vdo vector<double>

#define pqll priority_queue<ll>
#define pqllg priority_queue<ll, vector<ll>, greater<ll>>

constexpr ll INF = (1ll << 62);
// constexpr ll mod = 998244353;
// constexpr ll mod = 67280421310721;
constexpr ll mod = 1000000007;
constexpr double pi = 3.14159265358979323846;
template <typename T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
void pt(T val) {
    cout << val << "\n";
}
template <typename T>
void pt_vll(vector<T> &v) {
    ll vs = v.size();
    rep(i, vs) {
        cout << v[i];

        if (i == vs - 1)
            cout << "\n";
        else
            cout << " ";
    }
}
template <typename T>
void pt_vvll(vector<vector<T>> &v) {
    ll vs = v.size();
    rep(i, vs) pt_vll(v[i]);
}

ll gcd(ll a, ll b) {
    if (a % b == 0) return b;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

ll modpow(ll x, ll n) {
    ll ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ret;
}
ll minv(ll a, ll m) { return modpow(a, m - 2); }

void make_prime(vector<ll> &ret, ll n) {
    ll x = n;
    for (ll i = 2; i * i <= x; i++) {
        while (n % i == 0) {
            n /= i;
            ret.push_back(i);
        }
    }
    if (n != 1) {
        ret.push_back(n);
    }

    return;
}

ll M;
ll mypow(ll a, ll n) {
    ll ret = 1;
    rep(i, n) {
        if (ret > M / a) return -1;
        ret *= a;
    }
    return ret;
}
using pp = pair<P, ll>;
map<pp, ll> mp;
void dijkstra(vector<vector<P>> &G, ll start, vector<ll> &dist) {
    priority_queue<P, vector<P>, greater<P>> que;
    que.push({0, start});
    ll n = G.size();

    dist.assign(n, INF);
    dist[start] = 0;

    while (que.size()) {
        P now = que.top();
        que.pop();
        if (dist[now.se] < now.fi) continue;

        for (auto nx : G[now.se]) {
            ll D = mp[{{nx.fi, now.se}, nx.se}];
            ll d2 = (dist[now.se] + D - 1) / D * D;
            if (chmin(dist[nx.fi], d2 + nx.se))
                que.push(make_pair(dist[nx.fi], nx.fi));
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M, X, Y;
    cin >> N >> M >> X >> Y;
    vector<vector<P>> G(N);
    rep(i, M) {
        ll a, b, t, k;
        cin >> a >> b >> t >> k;
        G[--a].push_back({--b, t});
        G[b].push_back({a, t});
        mp[{{a, b}, t}] = mp[{{b, a}, t}] = k;
    }

    vll dist;
    dijkstra(G, --X, dist);
    // pt_vll(dist);
    if (dist[--Y] < INF)
        pt(dist[Y]);
    else
        pt(-1);
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;
	char k;
	bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
int s,a[505],b[505],pr[505*505];bool ty;
void Swap(int x,int y){b[a[x]]=y;b[a[y]]=x;swap(a[x],a[y]);pr[++*pr]=x;ty^=1;}
void Swap2(int x){Swap(x-1,x);Swap(x,x+1);Swap(x-1,x);Swap(x,x+1),Swap(x-1,x);}
int main(){
	for(int T=read;T--;){
		s=read;*pr=0;ty=1;
		for(int i=1;i<=s;++i)b[a[i]=read]=i;
		for(int i=1;i<s-1;++i){
			if(b[i]==i)continue;
			if((b[i]^ty)&1)
				for(int j=b[i]-1;j>=i;--j)Swap(j,j+1);
			else{
				int w=b[i]-1;
				if(w!=i)Swap(w-1,w);
				else if(w==s-3){
					Swap(w+1,w+2);
					Swap(w+2,w+3);
					Swap(w+1,w+2);
					w=s-1;
				}else if(w==s-2){Swap2(i);w=i-1;}
				else Swap(w+3,w+4);
				for(int j=w;j>=i;--j)Swap(j,j+1);
			}
		}if(a[s-1]>a[s])
			if((b[s-1]^ty)&1)Swap(b[s-1]-1,b[s-1]);
			else Swap2(s-1);
		printf("%d\n",*pr);
		for(int i=1;i<=*pr;++i)printf("%d ",pr[i]);
		putchar('\n');
	}
	return 0;
}/*

      x
1 3 2 5 4
a c b
c a b
c b a
b c a
b a c
a b c
*/