P6664 [Tsinghua Training 2016] Warmth Will Guide Us Forward

The cold winter once again swept across the northern land. The ruthless north wind pierced through people’s winter clothes. Poor folks cried helplessly in the winter night. “I’m freezing to death!” At this moment, a god of flame appeared on the far horizon. “I will grant you warmth and hope!” Flame power burst out from his body, passing through solid steel and reaching every household. Then people cheered, “The heating is here!”

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.

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).

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

Constraints. For the `find` operation: $0≤id