#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;

using pii = pair<int, int>;
const int N = 1010, SZ = (1 << 18) + 5;
static char buf[SZ], *bgn = buf, *til = buf;
char getc() {
    if(bgn == til)  bgn = buf, til = buf + fread(buf, 1, SZ, stdin);
    return bgn == til ? EOF : *bgn++;
}
template<typename T>
void read(T &x) {
    char ch = getc();  T fh = 0;   x = 0;
    while(ch < '0' || ch > '9')    fh |= (ch == '-'), ch = getc();
    while(ch >= '0' && ch <= '9')   x = x * 10 + ch - '0', ch = getc();
    x = fh ? -x : x;
}
template<typename Type, typename... argc>
void read(Type &x, argc &...args)   {read(x), read(args...);}
template<typename T>
void print(T x) {
    if(x < 0)  putchar('-'), x = -x;
    if(x / 10)  print(x / 10);
    putchar(x % 10 + '0');
}
int n, p[N], u[N], v[N], siz[N], fr[N], book[N], tot, mn, root, vis[N], sum[N], cnt;
vector<pii> edge[N];
vector<int> opr[N * 4], tmp, lin;
void dfszx(int x, int fa) {
    siz[x] = 1; int res = 0;
    for(auto [y, i] : edge[x])
        if(y != fa && !vis[y])  dfszx(y, x), res = max(res, siz[y]), siz[x] += siz[y];
    res = max(res, tot - siz[x]);
    if(res < mn)    mn = res, root = x;
}
void getroot(int x) {dfszx(x, 0), tot = siz[x], mn = N, dfszx(x, 0);}
void dfs(int x, int fa, int id) {
    fr[x] = id, tmp.pb(x);
    for(auto [y, i] : edge[x])  if(y != fa && !vis[y])  dfs(y, x, id);
}
void Dfs(int x, int fa) {
    for(auto [y, i] : edge[x])  if(y != fa && !vis[y]) {
        if(sum[y] && !sum[x] && !book[y] && !book[x])   lin.pb(i), book[x] = book[y] = 1;
        Dfs(y, x);
    }
}
void solve(int x, int num) {
    vis[x] = 1, fr[x] = x, tmp.clear(), tmp.pb(x);
    for(auto [y, i] : edge[x])  if(!vis[y]) dfs(y, x, y);
    // cerr << x << " " << num << "\n";
    while(1) {
        for(int i : tmp)    book[i] = 0, sum[i] = fr[i] != fr[p[i]];
        int flag = 0;
        for(auto [y, i] : edge[x])  if(!vis[y] && !sum[y])   {flag = 1; break;}
        if(!flag)   break;
        lin.clear(), Dfs(x, 0);
        if(lin.empty()) break;
        ++num;
        for(int i : lin)    opr[num].pb(i), swap(p[u[i]], p[v[i]]);
    } 
    // cerr << num << "\n";
    while(1) {
        int res = 0;
        for(int i : tmp)    sum[i] = fr[i] != fr[p[i]], res += sum[i];
        if(!res)    break;
        for(int i : tmp)    book[i] = 0;
        if(!sum[x]) {
            int pre = num;
            for(auto [y, i] : edge[x])  if(!vis[y] && sum[y]) {
                // cerr << num + 1 << " : " << res << " | " << y << " " << p[y] << "\n";
                swap(p[x], p[y]), opr[++num].pb(i), book[x] = book[y] = 1;
                break;
            }
            // assert(num > pre);
            if(num == pre)  ++num;
            lin.clear(), Dfs(x, 0);
            for(int i : lin)    opr[num].pb(i), swap(p[u[i]], p[v[i]]);
            continue;
        }
        for(auto [y, i] : edge[x])  if(!vis[y] && fr[y] == fr[p[x]]) {
            // cerr << num + 1 << " : " << res << " " << y << " " << p[y] << "\n";
            assert(fr[p[y]] != fr[y]);
            opr[++num].pb(i), book[y] = book[x] = 1, swap(p[x], p[y]);   break;
        }
        for(int i : tmp)    sum[i] = fr[i] != fr[p[i]];
        lin.clear(), Dfs(x, 0);
        for(int i : lin)    opr[num].pb(i), swap(p[u[i]], p[v[i]]);
    }
    // cerr << num << "\n";
    cnt = max(cnt, num);
    for(auto [y, i] : edge[x])  if(!vis[y]) getroot(y), solve(root, num);
}
void mian() {
    for(int i = 1; i <= cnt; ++i)   opr[i].clear();
    read(n), cnt = 0;
    for(int i = 1; i <= n; ++i) read(p[i]), edge[i].clear(), vis[i] = 0;
    for(int i = 1; i < n; ++i) {
        read(u[i], v[i]);
        edge[u[i]].pb({v[i], i}), edge[v[i]].pb({u[i], i});
    }
    getroot(1), solve(root, 0);
    print(cnt), putchar('\n');
    for(int i = 1; i <= cnt; ++i) {
        print(opr[i].size()), putchar(' ');
        for(int x : opr[i]) print(x), putchar(' ');
        putchar('\n');
    }
}
int main() {
    #ifdef Kelly
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        freopen("err.txt", "w", stderr);
    #endif
    int T = 1;  read(T);
    while(T--)  mian();
    return 0;
}