给你一棵树,其中 $$$n$$$ 节点标记为 $$$1,2,\dots,n$$$。第 $$$i$$$ 条边连接节点 $$$u_i$$$ 和 $$$v_i$$$,并且具有未知的正整数权重 $$$w_i$$$。为了帮助您计算出这些权重,还给出了所有 $$$1 \le i \le n-1$$$ 的节点 $$$i$$$ 和 $$$i+1$$$ 之间的距离 $$$d_i$$$(树中节点 $$$i$$$ 和 $$$i+1$$$ 之间的简单路径上边的权重总和)。
求每条边的权重。如果有多个解决方案,请打印其中任何一个。如果没有与信息一致的权重$$$w_i$$$,则打印单个整数$$$-1$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$)。
接下来的 $$$n-1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$)。
最后一行包含 $$$n-1$$$ 整数 $$$d_1,\dots,d_{n-1}$$$ ($$$1 \le d_i \le 10^{12}$$$)。
保证给定的边形成一棵树。
输出
如果没有解决方案,则打印单个整数 $$$-1$$$。否则,输出包含权重 $$$w_1,\dots,w_{n-1}$$$ 的 $$$n-1$$$ 行。
如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
5 1 2 1 3 2 4 2 5 31 41 59 26
输出 #1
31 10 18 8
输入 #2
3 1 2 1 3 18 18
输出 #2
-1
输入 #3
9 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 2 236 205 72 125 178 216 214 117
输出 #3
31 41 59 26 53 58 97 93
注意
在第一个示例中,树如下:
在第二个示例中,请注意 $$$w_2$$$ 不允许为 $$$0$$$,因为它必须是正整数,因此无解。
在第三个示例中,树如下: