A13212 | 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.

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.

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.