七夕之夜，银河如练。传说中，牛郎与织女会在鹊桥相会。

今夜，在展望台仰望星空的 Mare 画下了一张星图，图中标记着 $n$ 颗星星，它们通过 $n-1$ 条边相连，形成了一棵星树。

Mare 在星图旁写了一个字符串 $s$，长度为 $n$，由 $0$ 和 $1$ 组成。

请构造一个点亮星星的排列 $p$（或判定无解），使得按照某个顺序 $p_1, p_2, \dots, p_n$ 依次点亮星星时，满足：

• 对于 $i=1\sim n$，点亮 $p_1, p_2\dots,p_i$ 后：
• 若 $s_i = 0$，则存在树上的一条边，移除它后，两个连通块中点亮的星数相等。
• 若 $s_i = 1$，则不满足上述条件。

输入格式

第一行两个整数 $T,O$，表示数据组数和子任务编号。对于样例，$O=0$。

对于每组数据：

第一行一个正整数 $n$。

接下来 $n-1$ 行，每行两个整数 $u,v$，描述一条边 $(u,v)$。

接下来一行一个长度为 $n$ 的字符串 $s$。

输出格式

对于每组数据，先输出一行 YES/NO，表示是否存在合法排列。

对于有解的数据，在第二行输出一个排列。

2 0
5
1 2
1 3
2 4
2 5
10101
7
1 2
1 3
2 4
2 5
3 6
3 7
1011101

YES
1 2 3 4 5
YES
1 2 4 5 3 6 7

样例二 $\sim$ 样例三

见附件下载。

数据范围

对于所有数据，满足 $1\le n\le 2\times 10^5$。

特别地，若对于一个子任务，判断正确是否有解，可获得 $50\%$ 的部分分。

请注意，即使只判断了有解，在有解的测试点也应当按照格式输出一个 $1\sim n$ 的排列，否则会被判为 $0$ 分。

• 特殊性质 A：$\forall i\in [2,n]$，先将 $i$ 和 $i-1$ 连边，最后随机打乱所有点编号。
• 特殊性质 B：$\forall i\in [2,n]$，先将 $i$ 和 $[1,i-1]$ 内一个点等概率随机连边，最后随机打乱所有点编号；保证单组 $n\ge 999$；保证测试点个数不超过 $5$ 个。
• 特殊性质 C：保证 $s_n = 0$。

时间限制：$2\texttt{s}$

空间限制：$1\texttt{GB}$