#P4683. 动态仙人图
动态仙人图
题目描述
有一张包含 个结点的无向加权图,初始没有边。若每条边至多属于两个简单环,则称这张图为仙人图。重边按各自的边区分,两条连接同一对结点的边也可以组成一个简单环。
需要依次处理以下三类操作。
link a b w:尝试添加一条连接 、权重为 的边。若 或添加后不满足仙人图条件,输出failed并保持原图。否则添加该边并输出ok。cut a b w:尝试删除一条连接 、权重为 的边。如果存在,任意删除其中一条并输出ok。如果不存在,输出failed。distance? a b:输出 到 的最短路长度。如果两点不连通,输出-1。如果 ,输出0。
输入格式
第一行两个整数 ,分别表示结点数和操作数。接下来 行,每行描述一条操作,格式如上。
输出格式
每个操作输出一行。
数据范围
,,。本站评测数据中,添加和删除操作的权重参数均为整数,满足 。边长相关的计算结果在有符号 32 位整数范围内。
样例
5 12
link 1 2 3
link 2 3 3
distance? 1 3
cut 2 3 3
distance? 1 3
cut 2 3 2
link 2 3 2
cut 2 3 3
link 3 4 3
link 4 1 5
link 1 3 8
link 2 4 7
ok
ok
6
ok
-1
failed
ok
failed
ok
ok
ok
failed
6 25
link 1 2 3
link 1 2 2
link 1 2 5
cut 1 2 2
cut 1 2 5
link 1 2 3
link 1 2 3
cut 1 2 3
cut 1 2 3
cut 1 2 3
cut 1 2 3
link 1 2 4
link 1 3 5
distance? 2 3
link 2 4 1
link 3 4 2
link 2 3 3
link 1 4 7
link 1 4 7
cut 1 4 7
link 5 6 8
distance? 3 6
distance? 2 6
cut 2 4 1
distance? 1 5
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
failed
ok
ok
9
ok
ok
ok
failed
failed
failed
ok
-1
-1
ok
-1