Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Дан связный неориентированный граф из `N` вершин и `N` ребер.
Между двумя вершинами может быть не более одного ребра, также ребра соединяют только различные вершины (нет петель).
Необходимо покрасить некоторые вершины в красный цвет так, чтобы каждая вершина была соединена ребрами ровно с одной красной вершиной.
Первая строка ввода содержит одно целое число `N` (`3 <= N <= 100000`) -- количество вершин в графе.
Далее следует `N` строк, каждая строка содержит два целых числа в диапазоне от 1 до `N` -- номера вершин, соединенных ребром.
Вывести одно число -- минимальное количество вершин, которые нужно покрасить в красный цвет.
Если раскрасить граф указанным способом невозможно, то вывести число `-1`.
```sample Пример ввода 1
4
1 2
2 3
3 4
4 1
```
```sample Пример вывода 1
2
```
```sample Пример ввода 2
3
1 2
2 3
3 1
```
```sample Пример вывода 2
-1
```
```sample Пример ввода 3
7
1 2
2 3
2 4
3 4
4 5
5 6
6 7
```
```sample Пример вывода 3
4
```
Пояснение к примеру 1: Нужно покрасить вершины с номерами 1 и 2.
Начало
Рабочее место участника
Поиск в глубину (DFS)