Это многое говорит об обществе.
Однажды черепаха подарила вам дерево с \(n\) вершинами и корнем в вершине \(x\). Вершина \(i\) имеет начальное целое неотрицательное значение \(a_i\).
Вы хотите сделать так, чтобы значения всех вершин стали равны \(0\). Для этого вы выполните ряд операций над деревом, где каждая операция будет выполняться над определенной вершиной. Определим операцию над вершиной \(u\) как выбор одной вершины в поддереве\(^{\text{∗}}\) \(u\), и увеличение или уменьшение ее значения на \(1\). Порядок выполнения операций над вершинами следующий:
- Для \(1 \le i \le n\), \(i\)-я операция будет выполнена над вершиной \(i\).
- Для \(i > n\), \(i\)-я операция будет выполнена над той же вершиной, что и операция \(i - n\).
Более формально, \(i\)-я операция будет выполнена над \((((i - 1) \bmod n) + 1)\)-й вершиной.\(^{\text{†}}\)
Обратите внимание, что нельзя пропускать операции; то есть нельзя выполнить \(i\)-ю операцию, не выполнив сначала операции \(1, 2, \ldots, i - 1\).
Найдите минимальное количество операций, которое необходимо выполнить, чтобы значения всех вершин стали равны \(0\), при условии, что вы выполняете операции оптимально. Если после конечного числа операций невозможно сделать значения всех вершин равными \(0\), выведите \(-1\).
Выходные данные
Для каждого набора входных данных выведите одно целое число, обозначающее минимальное количество операций, необходимое для того, чтобы сделать значения всех вершин равными \(0\). Если невозможно сделать значения всех вершин равными \(0\), выведите \(-1\).
Примечание
В первом наборе входных данных вы можете выполнить следующую последовательность операций:
- На \(1\) операции уменьшите значение вершины \(1\). Эта операция корректна, потому что \((((1 - 1) \bmod n) + 1) = 1\), и вершина \(1\) находится в поддереве вершины \(1\).
- На \(2\) операции уменьшите значение вершины \(2\). Эта операция корректна, потому что \((((2 - 1) \bmod n) + 1) = 2\), и вершина \(2\) находится в поддереве вершины \(2\).
- На \(3\) операции уменьшите значение вершины \(2\). Эта операция корректна, потому что \((((3 - 1) \bmod n) + 1) = 1\), а вершина \(2\) находится в поддереве вершины \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 1
1 2
1 2
3 2
2 1 3
2 1
3 2
4 1
1 1 0 1
1 2
2 3
1 4
12 6
14 4 5 6 12 9 5 11 6 2 1 12
3 9
10 6
6 12
4 3
3 1
5 11
9 7
5 6
1 8
2 8
5 1
1 1
0
|
3
6
5
145
0
|