const int N=2010;
int n,pos[N],head[N],tot; //pos:数字 i 初始节点位置
struct edge
{
int to,nxt;
}e[N<<1];
struct node_graph //每个点所建立的图
{
int fir,las,num,fa[N]; //钦定的第一条边，最后一条，边（点）数，并查集
bool ine[N],oue[N]; //是否有入/出边
void clear() { fir=las=num=0; for ( int i=1; i<=n; i++ ) fa[i]=i,ine[i]=oue[i]=0; }
int find( int x ) { return x==fa[x] ? x : fa[x]=find(fa[x]); }
}g[N];
void add( int u,int v )
{
e[++tot].to=v; e[tot].nxt=head[u]; head[u]=tot; g[u].num++;
e[++tot].to=u; e[tot].nxt=head[v]; head[v]=tot; g[v].num++;
}
int dfs1( int u,int fro_edge )
{
int res=n+1;
if ( fro_edge && (!g[u].las || g[u].las==fro_edge ) ) //还没有终点或者终点就是这条边
{
if ( !g[u].oue[fro_edge] && !(g[u].fir && g[u].num>1 && g[u].find(fro_edge)==g[u].find(g[u].fir)) )
//这条边（点）在这个点的图里面还没有出边，而且不能：
//有起点，总点数大于1，且已经在一条链里面了
res=u;
}
for ( int i=head[u]; i; i=e[i].nxt )
{
int v=e[i].to,to_edge=i/2;
if ( fro_edge==to_edge ) continue; //防止沿着双向边搜回去，tot是从1开始的，所以同一条双向边/2向下取整是一样的
if ( !fro_edge ) //前面没有链的情况
{
if ( !g[u].fir || g[u].fir==to_edge ) //没有钦定起点，或者起点就是当前边
{
if ( g[u].ine[to_edge] ) continue; //如果有入边了就不能当起点
if ( g[u].las && g[u].num>1 && g[u].find(to_edge)==g[u].find(g[u].las) )
continue; //起点和终点已经在一条链里面了
res=min( res,dfs1( v,to_edge ) );
}
else continue;
}
else //前面有链，往后接的情况
{
if ( fro_edge==g[u].las || to_edge==g[u].fir || g[u].find(fro_edge)==g[u].find(to_edge) )
continue; //如果上一条链的尾点是终点，那么后面不能接链；如果这条边是起点，那么不能被接；
//如果已经在一条链上了，也不能被接
if ( g[u].oue[fro_edge] || g[u].ine[to_edge] ) continue; //已经接过了
if ( g[u].fir && g[u].las && g[u].num>2 && g[u].find(fro_edge)==g[u].find(g[u].fir)
&& g[u].find(to_edge)==g[u].find(g[u].las) ) continue;
//从起点来的链，接上去终点的链，且还有点不在链上
res=min( res,dfs1( v,to_edge ) );
}
}
return res;
}
int dfs2( int u,int fro_edge,int endpos )
{
if ( u==endpos ) { g[u].las=fro_edge; return 1; } //到终点了，使命完成
for ( int i=head[u]; i; i=e[i].nxt )
{
int v=e[i].to,to_edge=i/2;
if ( fro_edge!=to_edge )
{
if ( dfs2( v,to_edge,endpos ) ) //后面可行
{
if ( !fro_edge ) g[u].fir=to_edge; //前面没有了，这个就是起点
else
{ //更新有无出入边的限制，并查集合并
g[u].oue[fro_edge]=g[u].ine[to_edge]=1; g[u].num--;
g[u].fa[g[u].find(fro_edge)]=g[u].find(to_edge);
}
return 1;
}
}
}
return 0;
}
int main()
{
int T=read();
while ( T-- )
{
tot=1; memset( head,0,sizeof(head) );
n=read();
for ( int i=1; i<=n; i++ )
g[i].clear(),pos[i]=read();
for ( int i=1,u,v; i u=read(),v=read(),add( u,v ); if ( n==1 ) { printf( "1\n" ); continue; } int p; for ( int i=1; i<=n; i++ ) { p=dfs1( pos[i],0 ); dfs2( pos[i],0,p ); //1用来搜方案，2用来加限制 printf( "%d ",p ); } printf( "\n" ); } return 0; }
