Description

Although the dorm building where Little R lives has already got heating, for some reasons, some windows in the building are still open (for example, the bathroom window). This makes the temperature on some routes in the building still very low.

In Little R’s dorm building, there are $n$ locations and some roads. A road connects two locations, and Little R can travel along this road from either endpoint to the other endpoint. However, at the beginning, Little R is not familiar with any road in the building, so he will gradually discover these roads. When he discovers a road, he will also know its temperature and length. The temperatures of all roads are pairwise distinct.

Little R needs to move around in the building. Each time, he needs to go from one location to another. Little R hopes that each movement uses a warmest path. The definition of the warmest path is: sort the temperatures of all roads on the path in increasing order, and choose the path whose resulting sequence is lexicographically maximum. That is, the road with the lowest temperature on the path should be as warm as possible; under that condition, the road with the second-lowest temperature should be as warm as possible; and so on. Little R will not traverse any road more than once. Since all road temperatures are distinct, there is exactly one warmest path.

For each movement of Little R, you need to output the total length of the path he needs to walk. If Little R cannot complete this movement using the currently discovered roads, output -1.

Note that the lexicographic order in this problem is different from the usual definition. For two sequences $a,b(a≠b)$, if $a$ is a prefix of $b$, then $a$ is considered lexicographically larger. It also follows that the empty sequence is lexicographically largest.

Input Format

The first line contains two positive integers $n,m$, meaning Little R’s dorm building has $n$ locations and a total of $m$ events occur.

The next $m$ lines each describe an event. There are three types of events:

• find id u v t l means Little R discovers a road connecting $u$ and $v$, with index id. An edge with the same id appears at most once.
• move u v means Little R wants to go from $u$ to $v$. You need to compute the length of the warmest path. If $u$ cannot reach $v$, output -1.
• change id l means the length of the edge with index id becomes $l$ (it is guaranteed that this edge exists at the current time).

Output Format

For each query, output one integer per line, representing the length of the warmest path.

8 19
find 0 0 2 7 2
find 1 2 4 4 4
find 2 4 6 10 1
find 3 6 7 8 6
move 2 7
move 1 6
find 4 2 5 3 4
move 0 5
change 0 12
find 5 4 5 5 10
find 6 2 3 6 9
move 3 5
find 7 0 1 12 1
move 1 6
find 8 1 7 11 100
move 1 6
move 3 7
move 5 6
move 2 2

11
-1
6
23
18
106
122
11
0

15 45
find 0 1 0 8 5987
find 1 2 0 14 5455
find 2 3 0 27 8830
find 3 4 3 42 7688
find 4 5 0 25 1756
find 5 6 5 35 1550
find 6 7 4 43 9440
move 3 9
change 2 9113
move 10 13
move 3 3
move 11 10
find 7 8 7 6 7347
find 8 9 8 26 8935
move 8 4
change 3 4466
find 9 10 9 28 8560
move 6 5
find 10 11 10 31 6205
change 9 9228
find 11 12 10 23 948
find 12 13 12 45 5945
move 0 9
move 2 5
change 2 6118
find 13 14 13 12 6906
move 4 1
change 2 504
find 14 4 2 22 9796
move 10 7
move 1 14
move 13 3
find 15 12 9 39 8985
find 16 9 8 17 3710
change 1 5370
find 17 1 0 36 4669
find 18 7 6 37 8087
move 9 0
find 19 14 9 33 8234
find 20 0 4 24 5209
change 1 4883
find 21 6 3 9 2461
find 22 5 2 19 4291
change 1 7219
change 6 4846

-1
-1
0
-1
16787
1550
39301
7211
16571
25510
59706
46309
30692

Hint

Constraints.

For the find operation: $0≤id<m$, $0≤u,v<n$, $u≠v$, $0≤t≤1000000000$, $0≤l≤10000$.

For the move operation: $0≤u,v<n$.

For the change operation: $0≤l≤10000$.

For $100\%$ of the testdata: $1≤n≤100000$, $1≤m≤300000$.

Translated by ChatGPT 5