Problem B: 环路系统

Problem B: 环路系统

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 160  Solved: 67
[Submit] [Status] [Web Board] [Creator:]

Description

2077年,CS市已经不使用公路了,而是通过“环路”系统让各个地区实现连通,每一条环路都是双向的并且有一个固定的速度。这一天,PIPI驾驶着他的Tesla Model SSS准备从地区A开往地区B,相比于缩短时间,PIPI更希望在驾驶过程中行驶速度保持稳定,即行驶过程中最高速度和最低速度的差值越小越好(因为突然地提速/减速确实会让PIPI的驾驶体验很差)

Input

第一行输入CS市中的地区数量N和环路数量M(2N≤500 ,1M≤2000)。
接下来M行输入每条环路的起点s, 终点t, 速度speed 以及长度 len (1s,t≤N, s≠t, 1speed, len≤1e5)。
接下来一行输入一个整数Q,代表有Q次询问(1Q≤10)。
接下来Q行每行输入两个数字 u, v,代表PIPI想从地区u开往地区v(1≤u,v≤N)。

Output

对于每个询问,输出PIPI行驶过程中最高速度和最低速度的差值。如果无法到达,则输出-1。

Sample Input

4 4
1 2 2 1
2 3 4 2
1 4 1 3
3 4 2 4
2
1 3
1 2

Sample Output

1
0