\(7^{th}\) round (Croatian Olympiad in Informatics), April \(6^{th}\), 2013

In the distant future, food is transported between planets via o\(ne-wa\)y 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 o\(ne-di\)rectional. 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 “x” (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 A and B, they want to know what are all the possible values of the shortest path total transit
time from A to B, for all possible values of x. For example, in the situaton above, shortest path travel
from planet 2 to planet 1 could take 5 (if \(x \ge 5\)), 4, 3, 2, or 1 day (if \(x < 5\)).

If the output is incorrect, but the first number in each of the Q rows is correct, the solution will be
awarded 50% 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 50 points, the following constraints hold: \(P \le 30\), \(R \le 300\), and \(T \le 50\).

The first line of input contains the two integers P and R, the number of planets and the number of
routes, respectively (\(1 \le P \le 500\), \(0 \le R \le 10\,000\)).
Each of the following R lines contains two integers C and D, the planet labels (\(1 \le C\), \(D \le P\), \(C \ne D\)),
and T, the travel time from C to D. For conventional routes, T is an integer (\(1 \le T \le 1\,000\,000\)), and
for hyperspace routes, T is the character “x”. Multiple lines can exist between the same two planets.
The following line contains the integer Q, the number of queries (\(1 \le Q \le 10\)).
Each of the following Q lines contains two integers A and B, the planet labels (\(A \ne B\)) representing a
query by the traders' guild: “what are the possible values of shortest path transit time from A to B?”.

The output must contain Q 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 A to B, the
number of different values and their sum is 0.
\(7^{th}\) round (Croatian Olympiad in Informatics), April \(6^{th}\), 2013

생성자가 기록되지 않았습니다.

출처 COCI 2012/2013 Olympiad