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