B - Reversible Cards Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

1 から N の番号がついた 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 の側を表にすることで 4 色を達成できます。

入力例 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

Score : 400 points

Problem Statement

We have N cards numbered 1 to N. Each side of each card has a color represented by a positive integer.

One side of Card i has a color a_i, and the other side has a color b_i.

For each card, you can choose which side shows up. Find the maximum possible number of different colors showing up.

Constraints

  • 1 \leq N \leq 200000
  • 1 \leq a_i,b_i \leq 400000
  • All numbers in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_N b_N

Output

Print the answer.

Sample Input 1

4
1 2
1 3
4 2
2 3

Sample Output 1

4

We can choose the sides with 1, 3, 4, 2 to have four colors.

Sample Input 2

2
111 111
111 111

Sample Output 2

1

They are painted with just one color.

Sample Input 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

Sample Output 3

8