该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

有一个国家被一条何划分为南北两部分，在南岸和北岸总共有N对城镇，每一城镇 在对岸都有唯一的友好城镇。任何两个城镇都没有相同的友好城镇。每一对友好城 镇都希望有一条航线来往。于是他们向政府提出了申请。由于河终年有雾。政府决 定不允许有任两条航线交叉（如果两条航线交叉，将有很大机会撞船）。

你的任务是缟写一个程序来帮政府官员决定他们应拨款兴建哪些航线以使到没有出 现交叉的航线最多。

Input

输入描述：南北城市从左到右编号为0-n(n<=5000)

第一行为n,以下n行每行两个数，表示友好的两个城市

Output

一个数表示航线数

Sample Input

4

1 2

2 3

3 4

4 1

Sample Output

3