搬寝室 (move)

搬寝室 (move)

测试数据来自 h14z/1062

Description:

众所周知,每一次年级改换都要搬寝室。
搬寝室的话,自己在原来寝室的东西都要一并搬到新的寝室,例如蚊帐、床铺、三国杀、知音漫客,etc。但是东西太多,而走廊太窄,因此一段走廊在一定时间内只允许一位同学通过,例如熊博士从\(1\)寝室到\(5\)寝室与\(Doctor.Bear\)从\(2\)寝室到\(4\)寝室是不能同时进行的,因为他们会经过相同的一段;为了方便,\(Honeymoon\)从\(1\)寝室到\(4\)寝室与\(Yellow Moe\)从\(4\)寝室到\(5\)寝室也是不能同时进行的,因为他们都要经过四号寝室;而\(1-5\)与\(6-7\)是可以同时进行的。而且原寝室和目标寝室相同也是合法的,例如\(4-4\)是可以的,并且\(4-4\),\(1-5\)不能同时进行。
我们假定每次搬东西所需要的时间都为\(1\),而二班班长\(JIH\)想在大家都搬好之后召集同志们一起去踢球。所以他想知道从开始搬东西起,最少要经过多少时间他才能到绿茵场上。

Input:

第一行两个正整数\(N,M\),分别表示寝室的数目与搬寝室的次数。
接下来M行,每行两个正整数\(X,Y\),表示某人将东西从\(X\)寝室搬到了\(Y\)寝室。

Output:

一个整数,表示最少需要多少时间。

Sample Input:

6 4
1 3
2 4
5 6
6 4

Sample Output:

2

(1-3与6-4同时进行,2-4与5-6同时进行,总时间为2。)

数据规模:

对于\(30\%\)的数据,\(N\leq 20,M\leq 20\)
对于\(60\%\)的数据,\(N\leq 2000,M\leq 2000\)
对于\(80\%\)的数据,\(N\leq 100000,M\leq 200000\)
对于\(100\%\)的数据,\(N\leq maxlongint,M\leq 200000\)

信息

ID
1400
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者