← 返回题目列表

AtCoder · arc111_b

B. 双面卡

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

分数: 400 点

问题陈述

我们有 N 卡片编号 1 to N。每张卡片的每一面都有一个由正整数表示的颜色。

卡的一侧 i 有颜色 a_i,另一面有颜色 b_i.

对于每张卡,您可以选择显示哪一面。找出出现的不同颜色的最大可能数量。

约束

  • 1 \leq N \leq 200000
  • 1 \leq a_i,b_i \leq 400000
  • 输入的所有数字均为整数。

输入

输入由标准输入按以下格式给出:

N
a_1 b_1
a_2 b_2
:
a_N b_N

输出

打印答案。


示例输入 1

4
1 2
1 3
4 2
2 3

示例输出 1

4

我们可以选择带有 1, 3, 4, 2 有四种颜色。


示例输入 2

2
111 111
111 111

示例输出 2

1

它们只涂有一种颜色。


示例输入 3

12
5 2
5 6
1 2
9 7
2 7
5 5
4 2
6 7
2 2
7 8
9 7
1 8

示例输出 3

8