### 问题描述 七夕来临，天庭之中洋溢着浪漫的氛围。在充满诗情画意的七夕城里，有一对儿年轻的天仙——牛郎和织女，他们打算利用这个佳节为自己赚些零花钱。 这对天仙恋人商量后，决定分别在七夕城的不同集市售卖鲜花。七夕城共有 $N$ 个集市，通过 $N-1$ 条道路相互连通，其中 $1$ 号集市被视为主集市，七夕城的大门也坐落于此。每个集市都有一个热闹程度 $A_i$ 的值。 牛郎和织女的目标是：找到两个**不同的**集市 $u$ 和 $v$，其中 $u$ 为牛郎的售卖点，$v$ 为织女的售卖点，使得 $A_u$ 与 $A_v$ 的按位异或值 $A_u \oplus A_v$ 最小。同时，牛郎希望能够在从自己的集市 $u$ 前往 $1$ 号主集市的路上，恰好经过织女所在的集市 $v$，这样两人就可以一起离开七夕城。 现在，牛郎想知道，当织女位于 $v(v \in[1,n])$ 号集市售卖时，$A_u \oplus A_v$ 可能的最小值为多少，若不存在符合条件的 $u$ 号集市则输出 $-1$。 ### 输入格式 第一行输入一个整数 $N(2 \leq N \leq 10^5)$ 表示集市数量。 接下来 $N-1$ 行每行输入两个整数 $u,v( 1 \leq u,v \leq N, u\ne v)$ 表示集市 $u,v$ 之间存在一条道路。 最后一行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots,A_N(1 \leq A_i \leq 10^8)$ 表示每个集市的热闹程度。 ### 输出格式 输出一行 $n$ 个整数表示答案。 ### 输入样例 ```text 5 3 4 2 4 1 2 4 5 7 10 18 92 1 ``` ### 输出样例 ```text 6 11 -1 78 -1 ``` #### 说明 样例的图如下，当 $v=4$ 时，令 $u=3$ 可以使得 $A_u \oplus A_v$ 最小。