小象喜欢玩色卡。
他有n张牌,每张牌正好有两种颜色(正面的颜色和反面的颜色)。最初,所有卡片都正面朝上放在桌子上。小象只需一步就能将任何一张牌翻到另一边。小象认为桌子上的一组卡片很有趣,如果至少有一半的卡片具有相同的颜色(对于每张卡片,考虑上面的颜色)。
帮助小象找到使这组 n 张牌变得有趣所需的最少步数。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105) — 卡片的数量。接下来的 n 行包含所有卡的描述,每行一张卡。卡片由一对不超过 109 的正整数(双方的颜色)来描述。一行中的第一个数字是卡片正面的颜色,第二个数字是背面的颜色。卡正面的颜色可以与卡背面的颜色一致。
行中的数字由单个空格分隔。
输出
在一行上打印一个整数 - 寻求的最小移动数。如果不可能使该集合变得有趣,则打印 -1。
示例
输入 #1
3 4 7 4 7 7 4
输出 #1
0
输入 #2
5 4 7 7 4 2 11 9 7 1 1
输出 #2
2
注意
在第一个示例中,最初有三张卡片,颜色为 4, 4, 7。由于三张卡片中的两张具有相同的颜色 4,因此您不需要更改任何内容,因此答案为 0。
在第二个示例中,您可以翻开第一张和第四张牌。之后五张牌中的三张将是颜色 7。