Description
问题描述
有一个国家被一条河流分成南北两岸，南北两岸上各有若干个村庄，有些村庄的村民有亲戚在对岸。有亲戚在两岸的村庄想通过船只互通，他们向政府提出申请以获得批准。由于河面上常常有雾，政府决定禁止船只航线相交，所谓相交，是指河面上的相交，保留下来的航线可以有共同码头。
你的任务是编写一个程序，帮助政府官员决定批准哪些船只航线，使得不相交的航线数目最大。
输入文件
共n+1行：
第1行，一个数n，表示有n对分属两岸的村庄有亲戚（n<=5000）；
一下n行，每一行两个整数，表示两岸有亲戚的村庄编号；
输出文件
一个数，表示出最大可能满足上述条件的航线的数目。
输入样例
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
输出样例
4