SP9506 DIST2 - Jimmy´s Travel Plan

吉米生活在一个有着众多美丽城市的巨大王国中。他非常热爱旅行，渴望访问全国的每一个城市。他的秘书贾迪正在为他规划旅行路线。然而，这项任务并不简单，因为吉米可能会从任何城市出发，并向贾迪询问任意城市之间的路线信息。更麻烦的是，由于吉米可能从任何城市开始查询，贾迪必须实时提供几乎所有城市对之间的距离信息。对于这个庞大的国家来说，贾迪感到任务几乎无法完成，但为了让他的老板满意，他需要借助你的帮助。 这里有一个好消息：吉米很懒，只愿意去那些与起点城市之间距离不超过两步的目的地。这意味着，从出发城市到达目的地，最多只能经过一个中转城市。当然，如果两个城市之间有直接的路径，那些路径的长度都会是1。但不要掉以轻心，吉米还想知道在这样的条件下，有多少不同的路线可供选择。特别地，只有当两条路线中至少有一条路径不同，它们才被认为是不同的。此外，如果一个城市对之间有多条路径，那么这些路径应该视为独立的。

输入有多组测试数据。第一行是一个整数，表示测试数据的数量，然后是每组测试数据。每组测试数据第一行包含两个整数 $N$ 和 $M$，分别代表城市的数量和连接城市的路径数量。接下来的 $M$ 行中，每行包含两个空格分隔的整数 $A$ 和 $B$，表示城市 $A$ 和城市 $B$ 之间有一条无向路径。所有城市编号从1到 $N$。然后，接下来的一行中包含一个整数 $Q$，表示有 $Q$ 个查询。每个查询是用两个整数 $A$ 和 $B$ 表示的，分别位于单独的一行上，这代表询问城市 $A$ 到城市 $B$ 的最短距离和最短路径的数量。 测试数据用一个空行分隔。 你可以假设 $N, Q \leq 100000$，$M \leq 200000$。

对于每组测试数据，首先输出一行，指出测试数据的编号。然后，按照输入顺序输出针对查询的答复，每个查询一行。对于每个查询，如果存在至少一条长度不超过2的路径，则输出两个整数，分别表示最短路径的距离和可选择的不同最短路径数量，两个整数之间用空格分隔；如果不存在这样的路径，则输出一行文字：“The pair of cities are not connected or too far away.” 请仔细阅读示例数据获取更多细节。 **本翻译由 AI 自动生成**