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.
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$
Print a non-negative integer in a single line, denoting the number of valid sizes.
1 2 1 4
2 3 1 2
3 5 2 4
2 4 1 3
4 5 3 4
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.