Transportation Network

Time Limit: 4 Seconds
Memory Limit: 32768 KB

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

*
(adviser)*

**Site:** *http://zhuzeyuan.hp.infoseek.co.jp/index.files/our_contest_20040619.htm*

Author:

**XIN, Tao**
Source:

**Online Contest of Christopher's Adventure**
Submit
Status