伯兰有 $$$n$$$ 火车站。它们通过 $$$n-1$$$ 铁路段相互连接。铁路网络是连通的,即可以表示为无向树。
您有该网络的地图,因此对于每个铁路段,您都知道它连接哪些车站。
$$$n-1$$$ 部分中的每个部分都有一些风景美景的整数值。然而,这些值没有标记在地图上,您也不知道它们。所有这些值均从 $$$1$$$ 到 $$$10^6$$$(含)。
您向 $$$m$$$ 乘客询问了一些问题:第 $$$j$$$ 告诉您三个值:
- 他的出发站$$$a_j$$$;
- 他的到达站$$$b_j$$$;
- 从$$$a_j$$$到$$$b_j$$$的路径上的最小风景(火车沿着从$$$a_j$$$到$$$b_j$$$的最短路径行驶)。
您计划更新地图并为每个铁路段设置一些值$$$f_i$$$ - 风景美景。乘客的回答应该与这些价值观一致。
打印任何有效的值集 $$$f_1, f_2, \dots, f_{n-1}$$$,乘客的答案与该值一致或报告它不存在。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5000$$$) — Berland 的火车站数量。
接下来的 $$$n-1$$$ 行包含铁路路段的描述:第 $$$i$$$ 路段描述是两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n, x_i \ne y_i$$$),其中 $$$x_i$$$ 和$$$y_i$$$ 是由第 $$$i$$$ 个铁路段连接的车站的索引。所有铁路段均为双向。每个车站都可以通过铁路从任何其他车站到达。
下一行包含一个整数 $$$m$$$ ($$$1 \le m \le 5000$$$) — 被询问的乘客数量。接下来是 $$$m$$$ 行,第 $$$j$$$ 行包含三个整数 $$$a_j$$$、$$$b_j$$$ 和 $$$g_j$$$ ($$$1 \le a_j, b_j \le n$$$; $$$a_j \ne b_j$$$; $$$1 \le g_j \le 10^6$$$) — 出发站,抵达车站和沿途最美丽的风景。
输出
如果没有答案,则打印单个整数 -1。
否则,打印 $$$n-1$$$ 整数 $$$f_1, f_2, \dots, f_{n-1}$$$ ($$$1 \le f_i \le 10^6$$$),其中 $$$f_i$$$ 是第 $$$i$$$ 铁路段沿线的一些有效风景。
如果有多个答案,您可以打印其中任何一个。
示例
输入 #1
4 1 2 3 2 3 4 2 1 2 5 1 3 3
输出 #1
5 3 5
输入 #2
6 1 2 1 6 3 1 1 5 4 1 4 6 1 3 3 4 1 6 5 2 1 2 5
输出 #2
5 3 1 2 1
输入 #3
6 1 2 1 6 3 1 1 5 4 1 4 6 1 1 3 4 3 6 5 3 1 2 4
输出 #3
-1