The cold winter has once again ravaged the northern land. The relentless north wind pierces through people's warm clothing. Poor souls wail helplessly in the winter night: "I'm freezing to death!"
At this moment, a god of fire appeared on the distant horizon. "I shall grant you warmth and hope!" His body erupted with the power of fire, Passing through sturdy steel, reaching every household. Then, people cheered: "The heating is here!"
Description
Although the dormitory building where Xiao R lives has already received heating, for various reasons, some windows in the building remain open (such as those in the restrooms), causing the temperature on some paths in the dormitory to remain very low.
There are $n$ locations and some paths in Xiao R's dormitory building. A path connects two locations, and Xiao R can travel between any two locations via such a path. Initially, Xiao R is not familiar with any paths in the dormitory, so he will discover these paths gradually. When he discovers a path, he also learns its temperature and length. The temperatures of all paths are distinct.
Xiao R needs to move around the dormitory, and each time he needs to travel from one location to another. Xiao R wishes to take the "warmest path" for each trip. The warmest path is defined as the path whose sequence of edge temperatures, when sorted in ascending order, is lexicographically largest. That is, the lowest temperature on the path should be as high as possible; given that condition, the second-lowest temperature should be as high as possible, and so on. Xiao R will not traverse the same path twice. Since all path temperatures are distinct, there exists exactly one warmest path.
For each of Xiao R's trips, you need to calculate the total length of the path he must take. If Xiao R cannot complete the trip using the currently discovered paths, output $-1$.
Note: The definition of lexicographical order in this problem differs from the traditional one. For two sequences $a$ and $b$ ($a \neq b$), if $a$ is a prefix of $b$, then $a$ is considered lexicographically larger. Consequently, the empty sequence is the lexicographically largest.
Input
The first line contains two positive integers $n$ and $m$, representing $n$ locations in Xiao R's dormitory and $m$ events that occurred.
The next $m$ lines each describe an event, which can be one of three types:
find id u v t l: Xiao R discovers a path between $u$ and $v$ with ID $id$. Edges with the same $id$ will only appear once.move u v: Xiao R wants to travel from $u$ to $v$. You need to calculate the length of the warmest path. If $u$ and $v$ are not connected, output $-1$.change id l: The length of the edge with ID $id$ changes to $l$ (it is guaranteed that the edge exists at this time).
Output
For each query, output a single integer representing the length of the warmest path.
Examples
Input 1
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
Output 1
11 -1 6 23 18 106 122 11 0
Input 2
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
Output 2
-1 -1 0 -1 16787 1550 39301 7211 16571 25510 59706 46309 30692
Note
Example 3 is provided in the distributed files.
Constraints
For find operations: $(0\le id < m, 0\le u,v < n, u\ne v, 0\le t\le 10^9, 0 \le l \le 10000)$.
For move operations: $(0\le u,v < n)$.
For change operations: $(0 \le l \le 10000)$.
For 100% of the data, $1\le n\le 100000, 1\le m \le 300000$. There are 20 test cases in total, each worth 5 points.
| Test Case | $n$ | $m$ | Other |
|---|---|---|---|
| $1-2$ | $\le 20$ | $\le 50$ | No special constraints |
| $3-5$ | $\le 1000$ | $\le 3000$ | |
| $6-10$ | $\le 100000$ | $\le 300000$ | All find events occur before move events, and there are no change events |
| $11-14$ | All find events occur before move events |
||
| $15-20$ | No special constraints |