← 返回题目列表

Codeforces · 366/D

D. 迪马和陷阱图

中文机器翻译题面 查看原题

Dima 和 Inna 喜欢在一起度过时光。问题是,谢廖扎出于某种原因不太愿意离开他的房间。但迪玛和伊娜是如此相爱,以至于他们决定犯罪……

Dima 构建了一个陷阱图。他喊道:“嘿谢廖扎,看看我很酷的图表!”为了让他的室友感兴趣并把他踢到第一个节点。

陷阱图是由 n 个节点和 m 个边组成的无向图。对于边数 k,Dima 表示从 lk 到 rk (lk ≤ rk) 的整数范围。为了摆脱陷阱图,Seryozha 最初(在开始移动之前)应该选择一些整数(我们称之为 x),然后 Seryozha 必须从编号为 1 的起始节点到编号为 n 的最终节点走一段路。此时,只有当 lk ≤ x ≤ rk 时,Seryozha 才能沿着边 k 走。

Seryozha 是一位数学家。他将从第 1 个节点到第 n 个节点的某条路径的忠诚度定义为整数 x 的数量,这样如果他最初选择其中一个,他就会通过整条路径。帮助谢廖扎找到最大忠诚度的道路并尽快返回他的房间!

输入

输入的第一行包含两个整数 n 和 m (2 ≤ n ≤ 103, 0 ≤ m ≤ 3·103)。然后沿着 m 条线描述边缘。每行包含四个整数 ak、bk、lk 和 rk (1 ≤ ak, bk ≤ n, 1 ≤ lk ≤ rk ≤ 106)。这些数字表示陷阱图中第 k 条边连接节点 ak 和 bk,该边对应于从 lk 到 rk 的整数范围。

请注意,给定的图可以有循环和多条边。

输出

在输出的一行中打印一个整数 - 从第一个节点到第 n 个节点的所有路径中的最大忠诚度。如果这样的路径不存在或者最大忠诚度等于 0,则单行打印“干得好,Dima!”没有引号。

示例

输入 #1

4 4
1 2 1 10
2 4 3 5
1 3 1 5
2 4 2 7

输出 #1

6

输入 #2

5 6
1 2 1 10
2 5 11 20
1 4 2 5
1 3 10 11
3 4 12 10000
4 5 6 6

输出 #2

Nice work, Dima!

注意

第一个示例的说明。

总的来说,我们有 2 种方法从节点 1 到达节点 4:首先必须沿着范围为 [1-10] 的边 1-2,然后沿着两条边 2-4 之一。

其中一条包含范围[3-5],即我们可以用数字3、4、5通过。因此该路径的忠诚度为3。

如果我们沿着范围为 [2-7] 的边 2-4 走,那么我们可以通过数字 2、3、4、5、6、7。忠诚度为 6。这就是答案。

边 1-2 对答案没有影响,因为它的范围包括以下边的两个范围。