1340: 运河贸易桥梁规划问题(必做)

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:62 Solved:54

Description

在东方大陆有一条东西走向的运河,运河两岸是笔直的南北河岸,岸上各有 N 个不同的贸易港口。已知北岸每个港口恰好有一个位于南岸的友好贸易港,且不同北岸港口的友好港互不重复。 每对友好贸易港向商会申请在运河上修建一座直线桥梁连接双方,但由于运河上货船频繁,商会规定任意两座桥梁不得交叉,以确保航行安全。请设计方案,在满足桥梁不交叉的前提下,求出最多可修建的桥梁数量。

Input

第一行一个整数 N(1 ≤ N ≤ 5000),表示港口数量。 第 2 行到第 N+1 行,每行包含两个整数 A 和 B,分别表示南岸和北岸某对友好贸易港的坐标(0 ≤ A,B ≤ 10000)。

Output

仅一行,输出一个整数,表示最多可修建的桥梁数量。

Sample Input Copy

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

Sample Output Copy

4