Задачи
Видали їх всіх
Видали їх всіх
Дано дерево з n вершин.
Необхідно відповісти на наступне запитання: яку максимальну кількість ребер можна видалити з дерева так, щоб всі утворені компоненти зв'язності мали парну кількість вершин?
Вхідні дані:
В першому рядку знаходиться одне ціле число n (**1 ≤ n ≤ 105
**).
Наступні n-1 рядків містять по два числа u і v (**1 ≤ u, v ≤ n**), що описують вершини, які з'єднані ребром.
Гарантується, що задана конфігурація утворює дерево.
Вихідні дані:
Виведіть одне число k – максимальна кількість ребер, які можна видалити так, щоб всі компоненти зв'язності мали парну кількість вершин, або -1, якщо неможливо так видалити ребра, щоб всі компоненти зв'язності мали парну кількість вершин.
Входные данные #1
4 2 4 4 1 3 1
Выходные данные #1
1
Входные данные #2
3 1 2 1 3
Выходные данные #2
-1
Входные данные #3
10 7 1 8 4 8 10 4 7 6 5 9 3 3 5 2 10 2 5
Выходные данные #3
4
Входные данные #4
2 1 2
Выходные данные #4
0