Дано дерево из \(n\) вершин.
Необходимо ответить на следующий вопрос: какое максимальное количество ребер можно удалить из дерева так, чтобы все получившиеся компоненты связности содержали в себе четное количество вершин?
В первой строке задано число вершин \(n\) (\(1 \le n \le 10^5\)).
Следующие \(n - 1\) строк содержат по два числа \(u\), \(v\) (\(1 \le u, v \le n\)), описывающие вершины, соединенные \(i\)-м ребром.
Гарантируется, что заданная конфигурация образует дерево.
Выведите единственное число \(k\) — максимальное количество ребер, которое можно удалить, чтобы все компоненты связности имели четное число вершин, или \(-1\), если нельзя удалить ребра так, чтобы все компоненты связности имели четное число вершин.
В первом тестовом примере можно удалить ребро, соединяющее вершины \(1\) и \(4\), тогда граф распадется на две компоненты связности, в каждой из которых по две вершины.
Во втором тестовом примере нельзя удалить ребра так, чтобы все компоненты связности имели четное число вершин, поэтому ответ \(-1\).
4 2 4 4 1 3 1
1
3 1 2 1 3
-1
10 7 1 8 4 8 10 4 7 6 5 9 3 3 5 2 10 2 5
4
2 1 2
0
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач