Дано дерево на \(n\) вершинах, пронумерованных числами \(1,2,\dots,n\). \(i\)-е ребро соединяет вершины \(u_i\) и \(v_i\) и имеет некоторый неизвестный целый положительный вес \(w_i\). Вам также известны расстояния \(d_i\) между вершинами \(i\) и \(i+1\) для всех \(1 \le i \le n-1\) (это расстояние равно сумме весов рёбер на простом пути между вершинами дерева \(i\) и \(i+1\)).
Найдите вес каждого ребра. Если существует несколько решений, выведите любое из них. Если не существует весов \(w_i\), согласующихся со всеми данными, выведите одно целое число \(-1\).
Выходные данные
Если решения не существует, выведите одно целое число \(-1\). В противном случае выведите \(n-1\) строку, содержащую веса \(w_1,\dots,w_{n-1}\).
Если существует несколько решений, выведите любое из них.
Примечание
В первом примере дерево выглядит следующим образом:
Во втором примере вес \(w_2\) не может быть равен \(0\), поскольку должен быть целым положительным числом. Поэтому решения нет.
В третьем примере дерево выглядит следующим образом:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2
1 3
2 4
2 5
31 41 59 26
|
31
10
18
8
|
|
2
|
3
1 2
1 3
18 18
|
-1
|
|
3
|
9
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 2
236 205 72 125 178 216 214 117
|
31
41
59
26
53
58
97
93
|