题目描述

给定一张无向图，每条边在时间 $[l_i,r_i)$ 才能通过，通过花费 $1$ 的时间。你不能在原地停留。

你在时刻 $0$ 从 $1$ 号点，求最快何时能到达 $n$ 号点。

无法到达或被迫停留，输出 $-1$。

输入格式

第一行两个整数 $n,m$，分别表示顶点数和边数，$1 \le n \le 5\times 10^5$，$0 \le m \le 5 \times 10^5$。

接下来 $m$ 行，每行四个整数 $a_i,b_i,l_i,r_i$，$a_i\ne b_i$，$0 \le l_i < r_i \le 10^9$。

输出格式

一个整数表示答案，如果无解输出 $-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

3

2 1
1 2 1 100

-1