In the distant future, food is transported between planets via one-way trade routes. Each route directly connects two planets and has a known transit time.
The traders' guild plans to add some new routes utilizing a recently discovered technology – hyperspace travel. Travelling via hyperspace is also one-directional. Since it is still experimental, hyperspace travel time is not yet known, however it is known not to depend on distances between planets, so each hyperspace route will take an equal amount of time to traverse.
The picture below shows an example of three interconnected planets with transit times shown. The planets are labelled with positive integers, and the hyperspace travel time is denoted by (the picture corresponds to the second example input):
Transit time is measured in days and is always a positive integer.
The traders' guild wishes to analyze the consequences of introducing the new routes: for some two planets and , they want to know what are all the possible values of the shortest path total transit time from to , for all possible values of . For example, in the situation above, shortest path travel from planet to planet could take (if ), , , , or day (if ).
Input Specification
The first line of input contains the two integers and , the number of planets and the number of routes, respectively .
Each of the following lines contains two integers and , the planet labels ,
and , the travel time from to . For conventional routes, is an integer , and
for hyperspace routes, is the character x
. Multiple lines can exist between the same two planets.
The following line contains the integer , the number of queries .
Each of the following lines contains two integers and , the planet labels representing a query by the traders' guild: "what are the possible values of shortest path transit time from to ?".
Output Specification
The output must contain rows, one per query.
Each row must contain two integers: the number of different values and their sum. If the number of
different values is unbounded, output only inf
in that row. If there is no path from to , the
number of different values and their sum is .
Scoring
If the output is incorrect, but the first number in each of the rows is correct, the solution will be awarded of points for that test case. Note: The output must contain both numbers in each row where the number of values is bounded in order to qualify.
In test data worth a total of points, the following constraints hold: , , and .
Sample Input 1
4 4
1 2 x
2 3 x
3 4 x
1 4 8
3
2 1
1 3
1 4
Sample Output 1
0 0
inf
3 17
Explanation for Sample Output 1
- There is no possible path from to .
- For any positive integer , the shortest path from to takes time, so the solution is
inf
. - The shortest path from to can take (for ), (for ), or (for ) time. .
Sample Input 2
3 5
3 2 x
2 1 x
2 1 5
1 3 10
3 1 20
6
1 2
2 3
3 1
2 1
3 2
1 3
Sample Output 2
inf
5 65
15 185
5 15
inf
1 10
Comments