← 返回题目列表

Codeforces · 827/F

F. 肮脏的阿卡迪的厨房

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

Arkady 喜欢在他的厨房里走动。他迷宫般的厨房由几个与通道相连的重要场所组成。不幸的是,这些通道被牛奶淹没,无法通过。也就是说,只有在一定的时间间隔内才可以从任意方向通过每个通道。

所有通道的长度都是相等的,阿尔卡迪在一秒钟内穿过它们。出于安全考虑,阿尔卡迪永远不能停下来,也不能在通过通道时改变方向。换句话说,如果他开始在某个通道中行走,他应该到达该通道的尽头并立即离开该通道。

今天Arkady需要从地点1快速到达重要地点n。他计划在时刻0离开地点1,尽快到达地点n。请找出他在路上应该花费的最短时间。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 5·105, 0 ≤ m ≤ 5·105) – 分别是重要地点的数量和通道的数量。

之后是 m 行,每行描述一个段落。每行包含四个整数 a、b、l 和 r(1 ≤ a、b ≤ n、a ≠ b、0 ≤ l < r ≤ 109)——通道连接的位置以及可以使用该通道的时间段。

输出

打印一个整数 - Arkady 到达目的地所需的最短时间。如果他无法到达地点 n,则打印 -1。

示例

输入 #1

5 6
1 2 0 1
2 5 2 3
2 5 0 1
1 3 0 1
3 4 1 2
4 5 2 3

输出 #1

3

输入 #2

2 1
1 2 1 100

输出 #2

-1

注意

在第一个例子中,Arkady 应该经过重要的地方 1 → 3 → 4 → 5。

在第二个示例中,Arkady 无法开始行走,因为在时间点 0 不可能使用唯一的通道。