双机调度问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

F大学计算机学院实验中心有2 台相同的高性能超级计算机。学院高性能计算研究小组的科学家们在进行一项复杂计算研究时,用分治策略将计算任务分解为n个互不相同的子任务J1 , J2 , , Jn 。每个子任务都需要a 个时间单位来完成。由子任务间的逻辑关系给出执行这n 个子任务间的m个先后次序。双机调度问题要求在2 台相同的高性能超级计算机上确定n个子任务的最优调度方案,使全部完成n个子任务的时间最早。
对于给定的n 个互不相同的子任务J1 , J2 , , Jn ,以及这n 个子任务间的m个先后次序,计算全部完成n个子任务的最早时间。假设超级计算机开始处理子任务的时间为0。

Input

输入数据的第一行有2个正整数n和m,表示有n个互不相同的子任务和m个子任务间的先后次序。接下来的m行中每行有2 个正整数x 和y,表示子任务x 应在子任务y之前完成。n,m≤100000。

Output

将计算出的最早完成时间输出。在所有测试数据中,均假定完成每个子任务需要的时间单位为a=1。

Sample Input

17 21
6 4
7 4
12 11
11 8
9 4
9 5
10 5
4 1
4 2
5 3
16 13
8 5
12 6
12 7
12 9
16 14
13 12
14 12
15 12
7 5
8 4

Sample Output

9

Hint

Source