2019牛客多校8E
###name
explorer
###description
Gromah and LZR have entered the fifth level. Unlike the first four levels, they should do some moves in this level.
There are nvertices and m bidirectional roads in this level, each road is in format (u,v,l,r) , which means that vertex u and v are connected by this road, but the sizes of passers should be in interval [l,r] . Since passers with small size are likely to be attacked by other animals and passers with large size may be blocked by some narrow roads.
Moreover, vertex 1 is the starting point and vertex n is the destination. Gromah and LZR should go from vertex 1 to vertex n to enter the next level.
At the beginning of their exploration, they may drink a magic potion to set their sizes to a fixed positive integer. They want to know the number of positive integer sizes that make it possible for them to go from 1 to n .
Please help them to find the number of valid sizes.
###input
The first line contains two positive integers n,m , denoting the number of vertices and roads.
Following m lines each contains four positive integers u,v,l,r , denoting a bidirectional road (u,v,l,r) .
$1≤n,m≤10^5 ,1≤u\lt v≤n,1≤l≤r≤10^9$
###output
Print a nonnegative integer in a single line, denoting the number of valid sizes.
###sample input
5 5
1 2 1 4
2 3 1 2
3 5 2 4
2 4 1 3
4 5 3 4
###sample output
2
###hint
There are 2 valid sizes : 2 and 3.
For size 2, there exists a path 1→2→3→5.
For size 3, there exists a path 1→2→4→5.
###toturial
把l,r看作限制，从小到大枚举区间，则表现为删边加边，然后问图的联通情况。这可以用直接lct维护。
###code
1 
