网络上的数据传输是共用数据线的,当一台主机发送传输请求时网络上有其他主机在发送数据,就不能成功发送只能等待。如果网络经常处于占用情况,平均等待时间过长,可能说明网络负载过重、拓扑结构不好或延时算法有问题。为了检测是否有这些问题,可以在服务器之间发送一些数据查看响应时间。
不过现在,我们姑且简化问题,将网络看做是一维的线段,各个主机看做线段上的点。当主机i向主机j发送数据时,i->j窗口所有的主机此时都不能发送数据。每次数据传输为1单位时间(由于网线上数据传输速度很快,不计距离影响)。
下面给出一组测试,求完成所有传输请求需要使用的最少的时间。
多组测试数据,每组N+1行。
每组第一行数为题目描述中一组测试的请求数n
接下来n行,每行2个整数i,j,表示一次数据传输i->j。
1<=i,j<=N<=10000
对于每组数据,输出一行,为最小用时。
3
1 3
3 4
5 1
3