编程介的小学生 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
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 flink cdc无法实时同步mysql数据
  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名