#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
vector < int > Next[100005];
int what[100005];
int Ans[1000005];
int con[1000005];
int sz[1000005];
int ans=0,now,N,nn;
bool have[1000005];
int root;
vector < pair < int , int > > xx,yy;
vector < int > vis;
int xxx[100005];
int yyy[100005];
void DFS(int st,int here,int fa,int deg)
{
if(st!=here) if(what[here]==what[st]) now=min(now,deg);
for(auto i:Next[here])
{
if(i!=fa)
{
DFS(st,i,here,deg+1);
}
}
}
void F(int here)
{
int t,i;
if(here==N+1)
{
t=0;
for(i=1;i<=N;i++)
{
now=2e9;
DFS(i,i,-1,0);
t=max(t,now);
}
ans=min(ans,t);
if(t==ans) for(i=1;i<=N;i++) Ans[i]=what[i];
}
else
{
if(what[here]==-1)
{
what[here]=1;
F(here+1);
what[here]=0;
F(here+1);
what[here]=-1;
}
else F(here+1);
}
}
int DFS2(int here,int fa)
{
vis.push_back(here);
sz[here]=1;
for(auto i:Next[here])
{
if(!have[i]&&i!=fa)
{
sz[here]+=DFS2(i,here);
}
}
return sz[here];
}
void DFS3(int here,int fa)
{
int t=nn-sz[here];
xxx[here]=2e9;
yyy[here]=2e9;
for(auto i:Next[here])
{
if(!have[i]&&i!=fa)
{
DFS3(i,here);
t=max(t,sz[i]);
}
}
if(t<=nn/2) root=here;
}
void DFS4(int here,int fa,int deg,int fr)
{
if(what[here]==0) xxx[fr]=min(xxx[fr],deg);
if(what[here]==1) yyy[fr]=min(yyy[fr],deg);
for(auto i:Next[here])
{
if(!have[i]&&i!=fa)
{
if(fa==-1) DFS4(i,here,deg+1,i);
else DFS4(i,here,deg+1,fr);
}
}
}
void DFS5(int here,int fa,int deg,int fr)
{
if(what[here]==0)
{
if(xx[0].second==fr) con[here]=min(con[here],deg+xx[1].first);
else con[here]=min(con[here],deg+xx[0].first);
}
if(what[here]==1)
{
if(yy[0].second==fr) con[here]=min(con[here],deg+yy[1].first);
else con[here]=min(con[here],deg+yy[0].first);
}
for(auto i:Next[here])
{
if(!have[i]&&i!=fa)
{
if(fa==-1) DFS5(i,here,deg+1,i);
else DFS5(i,here,deg+1,fr);
}
}
}
void F2(int here)
{
vis.clear();
DFS2(here,-1);
nn=sz[here];
DFS3(here,-1);
xxx[0]=2e9;
yyy[0]=2e9;
DFS4(root,-1,0,0);
xx.clear();
yy.clear();
for(auto i:vis)
{
xx.push_back(make_pair(xxx[i],i));
yy.push_back(make_pair(yyy[i],i));
}
xx.push_back(make_pair(xxx[0],0));
yy.push_back(make_pair(yyy[0],0));
sort(xx.begin(),xx.end());
sort(yy.begin(),yy.end());
if(vis.size()==1)
{
have[root]=1;
return;
}
DFS5(root,-1,0,0);
have[root]=1;
for(auto i:Next[root]) if(!have[i]) F2(i);
}
int main()
{
int T,M,i,x=0,y=0,ok;
scanf("%d",&T);
while(T--)
{
ok=0;
ans=2e9;
scanf("%d",&N);
for(i=1;i<=N;i++) Next[i].clear();
for(i=1;i<N;i++)
{
scanf("%d %d",&x,&y);
Next[x].push_back(y);
Next[y].push_back(x);
}
for(i=1;i<=N;i++)
{
scanf("%d",&what[i]);
if(what[i]==-1) ok=1;
}
if(ok)
{
F(1);
if(ans==2000000000) printf("-1\n");
else
{
printf("%d\n",ans);
for(i=1;i<=N;i++) printf("%d ",Ans[i]);
printf("\n");
}
}
else
{
x=0;
y=0;
for(i=1;i<=N;i++)
{
have[i]=0;
con[i]=2e9;
if(what[i]==1) x++;
else y++;
}
if(x==1||y==1) printf("-1\n");
else
{
ans=0;
F2(1);
for(i=1;i<=N;i++) ans=max(ans,con[i]);
printf("%d\n",ans);
for(i=1;i<=N;i++) printf("%d ",what[i]);
printf("\n");
}
}
}
return 0;
}
