eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Видали їх всіх

Видали їх всіх

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Дано дерево з n вершин.

Необхідно відповісти на наступне запитання: яку максимальну кількість ребер можна видалити з дерева так, щоб всі утворені компоненти зв'язності мали парну кількість вершин?

Вхідні дані

В першому рядку знаходиться одне ціле число n (1n10^5).

Наступні n-1 рядків містять по два числа u і v (1u, vn), що описують вершини, які з'єднані ребром.

Гарантується, що задана конфігурація утворює дерево.

Вихідні дані

Виведіть одне число 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