B. Маленький Слоник и карточки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Слоник любит играть с цветными карточками.

У него есть n карточек, каждая имеет ровно два цвета (цвет на передней стороне и цвет на задней стороне). Изначально все карточки лежат на столе передней стороной вверх. За один шаг Маленький Слоник может перевернуть на другую сторону любую карточку. Маленький Слоник считает набор карточек на столе веселым, если хотя бы половина карточек имеет одинаковый цвет (для каждой карточки рассматривается цвет стороны, которой она лежит вверх).

Помогите Маленькому Слонику найти минимальное количество шагов необходимых для превращения набора из n карточек в веселый.

Входные данные

В первой строке задано единственное целое число n (1 ≤ n ≤ 105) — количество карточек. Следующие n строк содержат описание всех карточек, по одной карточке на строку. Карточки описываются парой целых положительных чисел, не превосходящих 109, — цветами на обеих сторонах. Первое число в строке — это цвет на передней стороне карточки, второе — на задней. Цвет на передней стороне может совпадать с цветом на задней.

Числа в строках разделяются единичными пробелами.

Выходные данные

В единственной строке выведите единственное целое число — искомое минимальное количество шагов. Если превратить набор в веселый невозможно, выведите -1.

Примеры
Входные данные
3
4 7
4 7
7 4
Выходные данные
0
Входные данные
5
4 7
7 4
2 11
9 7
1 1
Выходные данные
2
Примечание

В первом примере изначально лежат три карточки из цветами 4, 4, 7. Так как две из трех карточек имеют одинаковый цвет 4, менять ничего не нужно, поэтому ответ — 0.

Во втором примере можно перевернуть первую и четвертую карточки. После этого три из пяти карточек будут иметь цвет 7.