Warrior of Exoland
Time: 2 s
Memory: 125 MB
Memory: 125 MB
There is N warrior in Exoland. Every warrior has two numbers that are used to recognize them.
For the i-th warrior, the numbers are Xi and Yi.
Robert Jane, the great king of Exoland, wants to attack a neighboring country Zoomland. He wants to select warriors by assigning a unique identification number (Xi or Yi) for individuals.
Find the maximum possible number of warriors he can select.
For the i-th warrior, the numbers are Xi and Yi.
Robert Jane, the great king of Exoland, wants to attack a neighboring country Zoomland. He wants to select warriors by assigning a unique identification number (Xi or Yi) for individuals.
Find the maximum possible number of warriors he can select.
Input
The first line contains one integer N, the number of warriors in Exoland.Each of the following N lines will have two integers Xi and Yi, the numbers of i-th warriors have.
Constraint
1 ≤ N ≤ 2000001 ≤ Xi, Yi ≤ 400000
Output
Print the maximum possible number of warriors Jane can select.
Examples
Input | Output |
---|---|
4
1 2 2 4 3 2 1 3 |
4
|
Input | Output |
---|---|
2
200 200 200 200 |
1
|
Input | Output |
---|---|
20
6 19 8 20 16 8 3 20 9 13 10 11 8 15 20 11 18 17 8 14 15 16 20 1 5 2 7 11 14 7 4 11 14 15 20 5 15 1 12 1 |
17
|