22106번 - Дерево 다국어

문제

Искусству выращивания карликовых деревьев — бонсай уже более двух тысяч лет, и за это время было придумано множество различных стилей и техник. В этой задаче вам тоже предлагается вырастить дерево, но в несколько другом смысле.

Дерево — неориентированный связный граф без циклов. Изначально у вас есть дерево, состоящее из одной вершины. Вам доступны две операции с вашим деревом: удалить одно ребро и оставить любую из двух получившихся частей дерева, а также добавить две новые вершины и соединить их с вершиной, у которой до этого было не более одной смежной с ней вершины. Какое минимальное количество операций нужно, чтобы получить заданное дерево?

입력

Первая строка содержит целое число n (1 ≤ n ≤ 10⁵). Каждая из следующих n - 1 строк содержит по два числа u_i, v_i — ребра дерева: (1 ≤ u_i, v_i ≤ n для всех i от 1 до n - 1). Гарантируется, что заданный граф является деревом.

출력

Если такое дерево построить невозможно, выведите единственное число -1. В ином случае выведите минимальное количество операций, которое нужно, чтобы получить данное дерево.

제한

힌트