Найдите минимальную высоту корневого дерева\(^{\dagger}\) с \(a+b+c\) вершинами, которое удовлетворяет следующим условиям:
- \(a\) вершин имеют ровно \(2\) потомка,
- \(b\) вершин имеют ровно \(1\) потомка, и
- \(c\) вершин имеют ровно \(0\) потомков (не имеют потомков).
Если такого дерева не существует, вы должны сообщить об этом.
Дерево выше с корнем в верхней вершине, и каждая вершина помечена числом потомков. Здесь \(a=2\), \(b=1\), \(c=3\), и высота равна \(2\).
\(^{\dagger}\) Корневое дерево — это связный граф без циклов, с особой вершиной, называемой корнем. В корневом дереве, среди любых двух вершин, соединенных ребром, одна вершина является родителем (ближе к корню), а другая — потомком.
Расстояние между двумя вершинами в дереве — количество ребер в кратчайшем пути между ними. Высота корневого дерева — это максимальное расстояние от вершины до корня.
Выходные данные
Для каждого набора входных данных, если такое дерево не существует, выведите \(-1\). В противном случае выведите одно целое число — минимальную высоту дерева, удовлетворяющего описанным условиям.
Примечание
Первый набор входных данных изображен в условии. Можно доказать, что высота не может быть меньше \(2\).
Во втором наборе входных данных, можно сформировать дерево с одной вершиной и без ребер. Оно имеет высоту \(0\), что является оптимальным.
В третьем наборе входных данных, можно сформировать дерево с двумя вершинами, соединенными одним ребром. Оно имеет высоту \(1\), что является оптимальным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
2 1 3
0 0 1
0 1 1
1 0 2
1 1 3
3 1 4
8 17 9
24 36 48
1 0 0
0 3 1
|
2
0
1
1
-1
3
6
-1
-1
3
|