На стадион пришли n студентов. Они хотят сыграть в футбол, а для этого нужно разделиться на две команды с одинаковым количеством человек в каждой.
Известно, что в собравшейся компании имеются заклятые враги. У каждого студента имеется не более двух заклятых врагов. Причем, если студент A заклятый враг студента B, то студент B заклятый враг студента A.
Студенты хотят разделиться так, чтобы никакие два заклятых врага не оказались в одной команде. В случае, если нужным способом разделиться нельзя, некоторым студентам придется посидеть на скамейке запасных.
Определите какое наименьшее количество студентов придется отправить на скамейку запасных, чтобы можно было сформировать две команды описанным способом и матч наконец-то начался.
Выходные данные
Выведите единственное целое число — наименьшее количество студентов, которое нужно отправить на скамейку запасных, чтобы начать матч.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
1 2
2 4
5 3
1 4
|
1
|
|
2
|
6 2
1 4
3 4
|
0
|
|
3
|
6 6
1 2
2 3
3 1
4 5
5 6
6 4
|
2
|