CF1296F.Berland Beauty

There are $n$ railway stations in Berland. They are connected to each other by $n-1$ railway sections. The railway network is connected, i.e. can be represented as an undirected tree.

You have a map of that network, so for each railway section you know which stations it connects.

Each of the $n-1$ sections has some integer value of the scenery beauty. However, these values are not marked on the map and you don't know them. All these values are from $1$ to $10^6$ inclusive.

You asked $m$ passengers some questions: the $j$-th one told you three values:

• his departure station $a_j$;
• his arrival station $b_j$;
• minimum scenery beauty along the path from $a_j$ to $b_j$ (the train is moving along the shortest path from $a_j$ to $b_j$).

You are planning to update the map and set some value $f_i$ on each railway section — the scenery beauty. The passengers' answers should be consistent with these values.

Print any valid set of values $f_1, f_2, \dots, f_{n-1}$, which the passengers' answer is consistent with or report that it doesn't exist.

伯兰有 $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}$；若不存在这样的取值，则报告无解。

The first line contains a single integer $n$ ($2 \le n \le 5000$) — the number of railway stations in Berland.

The next $n-1$ lines contain descriptions of the railway sections: the $i$-th section description is two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n, x_i \ne y_i$), where $x_i$ and $y_i$ are the indices of the stations which are connected by the $i$-th railway section. All the railway sections are bidirected. Each station can be reached from any other station by the railway.

The next line contains a single integer $m$ ($1 \le m \le 5000$) — the number of passengers which were asked questions. Then $m$ lines follow, the $j$-th line contains three integers $a_j$, $b_j$ and $g_j$ ($1 \le a_j, b_j \le n$; $a_j \ne b_j$; $1 \le g_j \le 10^6$) — the departure station, the arrival station and the minimum scenery beauty along his path.

第一行包含一个整数 $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$），表示第 $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$），分别表示该乘客的出发车站、到达车站以及其路径上最小的风景优美度。

If there is no answer then print a single integer -1.

Otherwise, print $n-1$ integers $f_1, f_2, \dots, f_{n-1}$ ($1 \le f_i \le 10^6$), where $f_i$ is some valid scenery beauty along the $i$-th railway section.

If there are multiple answers, you can print any of them.

如果没有答案，则输出一个整数 $-1$。

否则，输出 $n-1$ 个整数 $f_1, f_2, \dots, f_{n-1}$（其中 $1 \le f_i \le 10^6$），$f_i$ 表示第 $i$ 段铁路沿线的某个合法风景美观度。

如果存在多个答案，输出任意一个即可。