시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 0 | 0 | 0 | 0.000% |
Искусству выращивания карликовых деревьев — бонсай уже более двух тысяч лет, и за это время было придумано множество различных стилей и техник. В этой задаче вам тоже предлагается вырастить дерево, но в несколько другом смысле.
Дерево — неориентированный связный граф без циклов. Изначально у вас есть дерево, состоящее из одной вершины. Вам доступны две операции с вашим деревом: удалить одно ребро и оставить любую из двух получившихся частей дерева, а также добавить две новые вершины и соединить их с вершиной, у которой до этого было не более одной смежной с ней вершины. Какое минимальное количество операций нужно, чтобы получить заданное дерево?
Первая строка содержит целое число n (1 ≤ n ≤ 105). Каждая из следующих n - 1 строк содержит по два числа ui, vi — ребра дерева: (1 ≤ ui, vi ≤ n для всех i от 1 до n - 1). Гарантируется, что заданный граф является деревом.
Если такое дерево построить невозможно, выведите единственное число -1. В ином случае выведите минимальное количество операций, которое нужно, чтобы получить данное дерево.
2 1 2
2
3 1 2 2 3
1
5 1 2 1 3 1 4 1 5
-1