Dirty Arkady's Kitchen
Contest: VK Cup 2017 - Finals
Difficulty rating: 3200
Tags: data structures, dp, graphs, shortest paths

Arkady likes to walk around his kitchen. His labyrinthine kitchen consists of several important places connected with passages. Unfortunately it happens that these passages are flooded with milk so that it's impossible to pass through them. Namely, it's possible to pass through each passage in any direction only during some time interval.

The lengths of all passages are equal and Arkady makes through them in one second. For security reasons, Arkady can never stop, also, he can't change direction while going through a passage. In other words, if he starts walking in some passage, he should reach its end and immediately leave the end.

Today Arkady needs to quickly reach important place n from place 1. He plans to exit the place 1 at time moment 0 and reach the place n as early as he can. Please find the minimum time he should spend on his way.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ 5·105, 0 ≤ m ≤ 5·105) — the number of important places and the number of passages, respectively.

After that, m lines follow, each of them describe one passage. Each line contains four integers a, b, l and r (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ l < r ≤ 109) — the places the passage connects and the time segment during which it's possible to use this passage.

Output format:
Print one integer — minimum time Arkady should spend to reach the destination. If he can't reach the place n, print -1.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
In the first example Arkady should go through important places 1 → 3 → 4 → 5.

In the second example Arkady can't start his walk because at time moment 0 it's impossible to use the only passage.

Example input:
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

Example output:
3

Example input:
2 1
1 2 1 100

Example output:
-1

Editorial:
Let's consider undirected edge(u;v) as two directed edges (u;v) and (v;u). Let Arkady came to the vertex u in moment of time t. Then he can come to v in moments of time t + 1, t + 3, ... until the edge is existing.
We will expand each directed edge: on one of them we can come in even moments of time and leave in odd; on the other edge we can come in odd moments of time and leave in even. So, each of the edges from initial graph has turned in 4 edges of the new graph.
Let's calculate for each edge dpi — the minimal moment of time when we can come on the edge i. Let's count this values with help of sorting of events like "edge appeared". For each vertex and parity we will remember the edge for which we can appear in this vertex in moments of time with such a parity which will disappear later than others.
When the event of appearing edge became we need to check if it is possible in this moment of time come to the beginning of this edge. If it is possible then dpi = li, where li — the minimal moment of time when it is possible to come to the beginning of the edge to go through this edge. Every time when some vertex became reachable with needed parity we say that value of dp is equals to this time for all edges which wait in this vertex this parity. Totally each edge will processed no more than two times, so totally solution works in O(nlogn).