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