Задано взвешенное дерево, состоящее из n вершин. Каждая вершина дерева покрашена либо в черный цвет, либо в красный. Красно-черное дерево называется красивым, если для любой его вершины найдется черная вершина, расстояние до которой не более x.
Расстоянием между двумя вершинами называется кратчайший путь между ними.
Вам задано красно-черное дерево. Требуется сделать его красивым за минимальное количество операций обмена цветом. За одну операцию обмена цветом разрешается выбрать две вершины разного цвета и каждую из них перекрасить в другой цвет. Другими словами, если выбрана красная вершина p и черная вершина q, за одну операцию разрешается перекрасить p в черный цвет, а q в красный.
Выведите минимальное количество требуемых операций.
Выходные данные
Выведите единственное целое число — минимальное количество требуемых операций обмена.
Если получить красивое дерево невозможно ни за какое количество операций, выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 0 0
1 2 2
2 3 2
|
1
|
|
2
|
4 2
0 1 0 0
1 2 2
2 3 2
3 4 2
|
-1
|