CF827F Dirty Arkady's Kitchen

Arkady 喜欢在他的厨房里四处走动。他那曲折的厨房由若干个重要地点组成，这些地点之间通过通道相连。不幸的是，有时这些通道会被牛奶淹没，使得无法通过。具体来说，每条通道仅在某个时间区间内才可以经过，并且可以从任意方向通过。 所有通道的长度都相等，Arkady 通过每条通道都只需要 1 秒。出于安全原因，Arkady 永远不能停下来，而且在穿越通道时不能改变行进方向。换句话说，如果他开始走过一条通道，他应当到达终点后立即离开该地。 今天 Arkady 需要尽快从地点 $1$ 出发，前往地点 $n$。他计划在时刻 $0$ 离开地点 $1$，并希望尽早到达地点 $n$。请你计算他最少需要多少时间才能到达终点。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 5 \cdot 10^{5}$，$0 \leq m \leq 5 \cdot 10^{5}$），分别表示重要地点的数量和通道的数量。 接下来有 $m$ 行，每行描述一条通道。每行包含四个整数 $a$，$b$，$l$ 和 $r$（$1 \leq a, b \leq n$，$a \ne b$，$0 \leq l < r \leq 10^{9}$），表示通道连接的两个地点 $a$ 和 $b$，以及在时间区间 $[l, r)$ 内可以走这条通道。

输出一个整数，表示 Arkady 到达终点所需的最短时间。如果无法到达，则输出 $-1$。

在第一个样例中，Arkady 应该依次经过地点 $1 \to 3 \to 4 \to 5$。 在第二个样例中，Arkady 无法出发，因为在时刻 $0$ 时唯一的通道无法通行。 由 ChatGPT 5 翻译