// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define ull unsigned long long
#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 100005
#define inf 0x3f3f3f3f

int n,m,p[maxn];
vi e[maxn];

int vis[maxn],nowt,rt;
int fa[maxn],sz[maxn],mxp[maxn],allsz;
void getrt(int u,int pa){
	sz[u]=1;
	mxp[u]=0;
	for(int v:e[u]){
		if(v!=pa&&vis[v]==nowt){
			getrt(v,u);
			sz[u]+=sz[v];
			mxp[u]=max(mxp[u],sz[v]);
		}
	}
	mxp[u]=max(mxp[u],allsz-sz[u]);
	if(mxp[u]<mxp[rt])rt=u;
}

int col[maxn];
void dfs(int u,int pa,int qwq){
	col[u]=qwq;
	fa[u]=pa;
	for(int v:e[u]){
		if(v!=pa && vis[v]==nowt){
			dfs(v,u,qwq);
		}
	}
}

int NOW;
vector< vector<pii> >vec;

vector<pii>stk;
void dostk(){
	for(auto [u,v]:stk) swap(p[u],p[v]);
	stk.clear();
}

int vis2[maxn];
void add(int T,int u,int v){
	while(vec.size()<T) vec.pb({});
	vec[T-1].pb(mkp(u,v));
	stk.pb(mkp(u,v));
	vis2[u]=vis2[v]=1;
}

void dfs2(int u,int pa){
	for(int v:e[u]) if(v!=pa && col[v]==col[u]) {
		dfs2(v,u);
		if(!vis2[u] && !vis2[v] && col[v]!=col[p[v]] && col[u]==col[p[u]]){
			add(NOW,u,v);
		}
	}
}

void solve(vi o,int T)
{
	if(!o.size()) return;
	if(o.size()==1) return;
	if(o.size()==2){
		int u=o[0],v=o[1];
		if(p[u]!=u){
			add(T,u,v);
			dostk();
			return;
		}
		return;
	}
	
//	cout<<"solve "<<T<<endl;
//	for(int x:o) cout<<x<<" "; cout<<"\n";
//	for(int x:o) cout<<p[x]<<" "; cout<<"\n";

	++nowt;
	for(int u:o)vis[u]=nowt;
	allsz=o.size();
	mxp[rt=0]=inf;
	getrt(o[0],0);
	getrt(rt,0);
	
	pii mnsz=mkp(inf,inf);
	for(int u:e[rt]) if(vis[u]==nowt) {
		dfs(u,rt,u);
		mnsz=min(mnsz,mkp(sz[u],u));
	}
	col[rt]=col[mnsz.se];
	
	vi sons;
	sons.pb(rt);
	for(int u:e[rt]) if(vis[u]==nowt && u!=mnsz.se) sons.pb(u);
	
	auto chk=[&](){
		for(int u:o)
			if(col[u]!=col[p[u]]) return 0;
		return 1;
	};
	
	while(!chk()){
		++T;
		NOW=T;
		for(int u:o) vis2[u]=0;
		for(int u:sons) dfs2(u,0);
		
		if(!vis2[rt]){
			for(int u:sons) if(u!=rt && !vis2[u] && !vis2[rt] && col[p[rt]]==col[u] && col[p[u]]!=col[u]) {
				add(NOW,rt,u);
				break;
			}
			for(int u:sons) if(u!=rt && !vis2[u] && !vis2[rt] && col[p[u]]!=col[u]) {
				add(NOW,rt,u);
				break;
			}
		}
		
		dostk();
	}
	
	vector<vi> mys;
	for(int u:sons){
		vi nxt;
		for(int v:o) if(col[v]==col[u]) nxt.pb(v);
		mys.pb(nxt);
		if(!nxt.size()){
			cout<<"u: "<<u<<endl;
			puts("???");
		}
	}
	for(auto it:mys) solve(it,T+1);
}

int mp[1005][1005];

void work()
{
	n=read();
	For(i,1,n)e[i].clear(); vec.clear();
	
	For(i,1,n)p[i]=read();
	For(i,1,n-1){
		int u=read(),v=read();
		mp[u][v]=mp[v][u]=i;
		e[u].pb(v),e[v].pb(u);
	}
	vi o;
	For(i,1,n) o.pb(i);
	solve(o,0);
//	For(i,1,n) cout<<p[i]<<" "; cout<<" p\n";
	cout<<vec.size()<<"\n";
	for(auto it:vec){
		cout<<it.size()<<" ";
		for(auto [x,y]:it) cout<<mp[x][y]<<" ";
		cout<<"\n";
	}
}

signed main()
{
    int T=read();
    while(T--)work();
    return 0;
}
/*
1
10
10 1 7 8 6 5 2 9 4 3
1 2
2 3
2 4
1 5
2 6
4 8
3 9
6 10
*/