UOJ Logo Universal Online Judge

UOJ

#63. 动态仙人掌 I

附件下载 统计

有一天,VFleaKing到森林里游玩,回来之后跟pyx1997说,我发现好多棵会动的树耶!pyx1997说,这有什么好稀奇的,我用手指头就能维护每棵树的形态。

于是又过了几天VFleaKing到沙漠里游玩,回来之后跟pyx1997说,我发现好多棵会动的仙人掌耶!pyx1997说,这有什么好稀奇的,我用脚丫子就能维护每棵仙人掌的形态。

于是VFleaKing很郁闷,他向你求助,请帮帮他吧。

如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。

如果一个无向图的每个连通块都是个仙人掌,且不存在自环,我们就称之为沙漠。

为了证明你确实能够维护仙人掌,我们给你 n 个结点,从 1n 标号。初始时没有任何边。每次进行如下操作之一:

  1. link v u w:在结点 v,u 间连一条权值为 w 的边。
    • 1v,unw 为正整数。
    • 如果连边完成后图仍为沙漠,则输出 "ok"(不含引号)。
    • 否则操作非法,撤销此次操作并输出 "failed"(不含引号)。
  2. cut v u w:在结点 v,u 间删掉一条权值为 w 的边。
    • 1v,unw 为正整数。
    • 如果存在这样的边则输出 "ok"(不含引号)(如果有多条权值为 w 的边删去任意一条)。
    • 否则操作非法,不进行操作并输出 "failed"(不含引号)。
  3. distance? v u:查询结点 v 到结点 u 的最短路信息。
    • 1v,un
    • 输出一个整数 lm
    • lm 代表最短路的长度。
    • 如果 v=ulm=0
    • 如果没有路可到达则 lm=1

输入格式

第一行两个用空格隔开的正整数 n,m 表示一共有 n 个结点,m 个操作。

接下来 m 行,每行代表一个操作。

输出格式

对于每个操作,输出相应的结果。

样例一

input

7 20
distance? 4 5
link 3 4 9
link 2 4 6
cut 2 4 6
distance? 5 7
link 6 7 8
link 6 4 1
link 2 1 2
link 2 3 5
link 7 5 2
link 2 5 9
distance? 4 5
distance? 5 6
distance? 5 4
distance? 2 7
link 1 2 7
distance? 4 6
cut 3 4 9
link 4 5 4
link 2 3 7

output

-1
ok
ok
ok
-1
ok
ok
ok
ok
ok
ok
11
10
11
11
ok
1
ok
ok
ok

样例二

见样例数据下载,这组超良心数据中包含了许多你需要考虑的细节。

样例三

见样例数据下载

限制与约定

1n100000,1m400000

保证 link 和 cut 操作中的 w 满足 1w10000,所以关于边权的计算不会超出 32 位有符号整数范围。

时间限制:5s

空间限制:256MB

下载

样例数据下载