任务描述

\n

虽然小R住的宿舍楼早已来了暖气，但是由于某些原因，宿舍楼中的某些窗户仍然开着（例如厕所的窗户），这就使得宿舍楼中有一些路上的温度还是很低。

\n

小R的宿舍楼中有$n$个地点和一些路，一条路连接了两个地点，小R可以通过这条路从其中任意一个地点到达另外一个地点。但在刚开始，小R还不熟悉宿舍楼中的任何一条路，所以他会慢慢地发现这些路，他在发现一条路时还会知道这条路的温度和长度。每条路的温度都是互不相同的。

\n

小R需要在宿舍楼中活动，每次他都需要从一个地点到达另一个地点。小R希望每次活动时经过一条最温暖的路径，最温暖的路径的定义为，将路径上各条路的温度从小到大排序后字典序最大。即温度最低的路温度尽量高，在满足该条件的情况下，温度第二低的路温度尽量高，以此类推。小R不会经过重复的路。由于每条路的温度互不相同，因此只存在一条最温暖的路径。

\n

对于小R的每次活动，你需要求出小R需要走过的路径总长度。如果小R通过当前发现的路不能完成这次活动，则输出 $-1$。

\n

注意本题中的字典序与传统意义上的字典序定义有所不同，对于两个序列$a,b(a \\neq b)$，若$a$是$b$的前缀则$a$的字典序较大，同时可以推出空串的字典序最大。

\n

输入格式

\n

第一行两个正整数 $n,m$。表示小R的宿舍楼中有 $n$ 个地点，共发生了 $m$ 个事件。

\n

接下来 $m$ 行，每行描述一个事件，事件分为三类。

\n

$\\texttt{find id u v t l}$ 表示小R发现了一条连接$u$和$v$之间的路，编号为$id$。相同$id$的边只会出现一次。
\n
$\\texttt{move u v}$ 表示小R要从$u$到达$v$，你需要计算出最温暖的路径的长度，若不能从$u$到达$v$，则输出$-1$。
\n
$\\texttt{change id l}$ 表示从$u$到$v$这条边的长度变为了$l$（保证在当前时间点这条边存在）。
\n

输出格式

\n

对于每个询问，输出一行整数，表示最温暖的路径长度。

\n\n\n

统计

递交统计

【清华集训2016】温暖会指引我们前行

信息

状态

开发

支持

还没有账户？

登录