1905_算法设计例题：电路分布（DP）

在一块电路板的上、下两端分别有n个接线柱。根据电路设计，要求用导线(i，π(i))将上端接线柱i与下端接线柱π(i)相连，如图所示。

其中，π(i)，1 ≤ i ≤ n是 {1, 2, …, n} 的一个排列。导线(i, π(i))称为该电路板上的第i条连线。对于任何1 ≤ i < j ≤ n，第i条连线和第j条连线相交的充分且必要条件是 π(i) > π(j)。

在制作电路板时，要求将这n条连线分布到若干绝缘层上，在同一层上的连线不相交。你的任务是要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，就是确定导线集Nets={ i, π(i),  1 ≤ i ≤ n }的最大不相交子集。

输入的第一行为整数n ( 1 ≤ n ≤ 500 )；接下来n行，每行两个整数表示导线(i, π(i))

输出只有一个整数，表示导线集最大不相交子集。

10
1 8
2 7
3 4
4 2
5 5
6 1
7 9
8 3
9 10
10 6

4