题目描述

有一个国家被一条何划分为南北两部分，在南岸和北岸总共有$\red N$个城镇，每一城镇在对岸都有唯一的友好城镇。

任何两个城镇都没有相同的友好城镇。

每一对友好城镇都希望有一条航线来往。

河终年有雾,于是他们向政府提出了申请。

政府决定不允许有任两条航线交叉（如果两条航线交叉，将有很大机会撞船）。

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

输入格式

南北城市从左到右编号为$\red {1-n}$

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

输出格式

输出只有一行，表示最长公共部分的长度。

样例

输入样例

4

1 7

2 6

3 5

4 4

输出样例

3

数据范围

$\red {60\%}$ 数据 $\red {1<=n<=5000}$

$\red {100\%}$数据 $\red{1<=n<=100000}$