| F.A.Qs | Home | ProblemSet | Status | Ranklist | Contest | Login | Register | 捐赠本站 |
|---|
在遥远的未来，行星之间的食品运输将依靠单向的贸易路线。每条路径直接连接两个行星，且其运输时间是已知的。
贸易商协会打算利用一项最近发现的新技术——超空间旅行，以增加一些新的航线。通过超空间旅行的航线也是单向的。由于该项技术仍处于试验阶段，超空间旅行的时间目前是未知的，但它不取决于行星之间的距离，所以每个超空间旅行的路线将花费等量的时间。
下图是三个相互联通的行星及其运输时间的例子。行星使用正整数标号，超空间旅行时间记为“x”（图片对应第输入样例）：
过境的时间以天计，并且始终是一个正整数。
贸易商协会希望对引进新航线的后果进行分析：对于某两个行星A和B，他们想知道对于任意的x，从A到B的最短路径的总中转时间的所有可能的值。例如，在上述情况中，从星球2到星球1的最短路径所需时间可以取值5（如果x≥5），4，3，2，或1天（如果x<5）
输入的第一行包含两个整数P和R，分别代表行星的数目和航线数量，1≤P≤500，0≤R≤10000。
接下来的R条航线路径包含两或三个整数：行星标号C和D（1≤C，D≤P，C≠D），和T，从C到D的旅行时间。对于传统的路径，T是一个整数（1≤T≤1000000），超空间航线中，T是字符“x”。 可以存在多行有两个相同的行星。
下面的行中包含的整数Q（1≤Q≤10），表示查询的数量。
以下Q行包含两个整数星球标号（A和B，A≠B），为贸易商协会的查询：“从A到B的最短路径时间的可能值是什么？
输出必须包含q行，每行一个查询。
每一行都必须包含两个整数：不同的可能值的数目和它们的总和。如果不同的可能值的数目是无限的，该行只输出“INF”。如果没有从A到B的路径，不同的可能值的数目及它们的总和都是0。