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.

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.