← 返回题目列表

Codeforces · 1296/F

F. 贝兰德美容

中文机器翻译题面 查看原题

伯兰有 $$$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