Problem10977--王者之证

10977: 王者之证

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

在一个充满魔法和奇迹的王国里,有一位年轻的王子,他即将继承王位。为了证明自己拥有足够的智慧和决断力,王子需要通过一个古老而神秘的试炼——“彩色卡片之谜”。

在这项试炼中,王子面前有 $N$ 张神奇的卡片。每张卡片都被赋予了不同的魔法颜色,这些颜色代表着王国中的不同元素,如火、风、水和土。每张卡片的两面都涂有不同的颜色,一面是颜色 $a_i$,另一面是颜色 $b_i$。为了成功通过试炼,王子需要展示尽可能多的不同颜色,展示的颜色越多,王子的智慧和领导能力就越能得到认可。

然而,这个挑战并不简单。王子需要仔细思考如何翻转卡片,以便最大化展示的不同颜色。他知道,每一种颜色都有其独特的力量,而只有当他展示出最多的颜色时,才能证明他有能力管理整个王国。

王子站在卡片前,思考着每一个可能的组合。他必须选择每张卡片的哪一面朝上,以便让更多的颜色展现在众人面前。这不仅是一个逻辑的挑战,更是对他判断力和智慧的考验。

王子知道他面临的是一项艰巨的任务。卡片的数量多达 $N$,而每种颜色的选择将直接影响最终的结果。王子需要找到一种策略,确保在有限的卡片中能够展示尽可能多的不同颜色。

他一个个翻转卡片,计算可能的颜色组合。他深知,每个决定都会影响最终的展示效果,只有最精确的计算才能让他展示出最多的颜色。当他最后一张卡片翻转完毕,他看到了展现出的色彩,那是整个王国中从未见过的壮丽景象。

当王子展示出他的成果时,王国的智者们对他刮目相看。通过这场试炼,王子不仅证明了自己的智慧和决策能力,也向所有人展示了他作为未来国王的潜力。

从此以后,王子不仅成为了王国的新国王,还因为他在彩色卡片试炼中的表现而被世人尊敬。他的故事也被代代相传,成为了王国中关于智慧与勇气的经典传奇。


简化一下

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

卡片 $i$ 的一面颜色为 $a_i$,另一面颜色为 $b_i$。

对于每张卡片,你可以选择哪一面朝上。求可能显示的不同颜色的最大数量。

Constraints

$1≤N≤200,000$
$1≤a_i,b_i≤400,000$
输入中的所有数字均为整数。

Sample 1 Input

4
1 2
1 3
4 2
2 3

Sample 1 Output

4

Sample 2 Input

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

Sample 2 Output

8

Source/Category