F. Красоты Берляндии
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии есть $$$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$$$) — количество железнодорожных станций в Берляндии.

В следующих $$$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$$$-й дороги.

Если существует несколько возможных ответов, вы можете вывести любой из них.

Примеры
Входные данные
4
1 2
3 2
3 4
2
1 2 5
1 3 3
Выходные данные
5 3 5
Входные данные
6
1 2
1 6
3 1
1 5
4 1
4
6 1 3
3 4 1
6 5 2
1 2 5
Выходные данные
5 3 1 2 1
Входные данные
6
1 2
1 6
3 1
1 5
4 1
4
6 1 1
3 4 3
6 5 3
1 2 4
Выходные данные
-1