编程介的小学生 2017-08-29 08:58 采纳率: 20.5%
浏览 736
已采纳

Transportation Network

A transportation network consists of a central node and some other nodes directly or indirectly (through some intermediate nodes) connected to the central node, and also the transporting channels which connect them. It is known that for any node in the transportation network there is exactly one path leads to the central. Every channel has its own length, the distance between any two nodes is defined as the total length their shortest path.

For example, in the following transportation network (the numbers in the parentheses represents the length of the channels):

  1
 /\

(2) / \ (3)
2 3
(2)| |(2)
| |
4 5

The distance between 2 and 3 is 5, the distance between 1 and 4 is 4, and the distance between 3 and 5 is 2.

Two transportation network can be combined, combining network A to network B means building a channel that connects the central of A and the central of B, and take the central of B as the central of the combined network. That combined network contains all the nodes and channels that is in network A or in network B.

Country-A has N (3 <= N <= 20,000) nodes that needs transporting between. Initially there is no channel between them, and each node is a solo transportation network. For the transporting the substance more expediently, Country-A has decided to build some transporting channels.

To maintain the information of the networks, Country-A has bought a super computer, which can receive and execute two kinds of instructions:

1) Q i j (1 <= i, j <= N, i <> j)

Querying the distance between node i and node j in the network. If they are not in the same network, output "Not connected." (Without quotation), output the distance otherwise.

2) U i j l (1 <= i, j <= N, node i and node j are not in the same network)

Combine the network containing i to the network containing j, makes the channel between them be l. (l is an integer, and 0 < l <= 1,000)
To avoid hackers' invasion which may cause the leak of the information, you should input the instruction U i' j' l instead of U i j l (where i' = (i + last_result) mod n + 1, j' = (j + last_result) mod n + 1 here last_result is the result of last valid query (i.e. the query that i and j are in the same network). Initially last_result = 0.

Your task is to write the program for the super computer.

Input

The first line of the input is an integer X (0 < X <= 6) represents number test cases of this problem. Then X blocks each represents
a test case.

The first line of each block contains two numbers N and M (5 <= M <= 40,000) representing country-A has N transportation nodes and the super computer will receive M instructions. Then M lines each represents an instruction, has the format Q i j or U i' j' l, which has been described above.

There're NO breakline between two continuous test cases.

Output

For each querying output one line an integer represents the distance or "Not connected." (Without quotation)

There're NO breakline between two continuous test cases.

Sample Input

2
4 6
U 3 4 4
Q 2 3
U 3 2 2
Q 1 2
U 2 3 1
Q 2 4
4 6
U 3 4 4
Q 2 3
U 3 2 2
Q 1 2
U 2 3 1
Q 2 4

Sample Output

4
6
7
4
6
7

  • 写回答

1条回答

  • threenewbee 2017-09-13 00:29
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥20 Python安装cvxpy库出问题
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥15 python天天向上类似问题,但没有清零
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 C#调用python代码(python带有库)
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?