В Берляндии есть \(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}\), которые согласуется с опросами или укажите, что такой не существует.
Выходные данные
Если ответа не существует, то выведите единственное число -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
|
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
|
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
|
-1
|