← 返回题目列表

Codeforces · 204/B

B. 小象和卡片

中文机器翻译题面 查看原题

小象喜欢玩色卡。

他有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。