#P3464. 动态仙人掌 I
动态仙人掌 I
动态仙人掌 I
题目描述
VFleaKing 去森林看见了会动的树,在沙漠看见了会动的仙人掌。pyx1997 说他会维护它们的形态,VFleaKing 想请你也试一试。
如果一个无向连通图的每条边至多属于一个简单环,就称它为仙人掌。如果无向图的每个连通分量都是仙人掌,并且图中没有自环,就称它为沙漠。允许两点之间有平行边,两条平行边可以组成一个环。
给定 个编号为 到 的节点,初始时没有边。依次处理以下操作。
link v u w尝试在 之间加入一条权值为 的边。如果加入后仍是沙漠,则保留新边并输出ok,否则撤销新增边并输出failed。cut v u w删除 之间满足给定权值的一条边。若有多条符合的边,任选一条删除。删除成功输出ok,否则不做修改并输出failed。distance? v u查询 到 的最短路长度,要求 。若两点不连通,输出-1。
输入格式
第一行包含两个正整数 ,分别表示节点数和操作数。
接下来 行,每行给出一个操作。节点编号 都在 到 之间, 为正整数。
输出格式
对每次操作按照上述规则输出一行。
样例 #1
6 49
link 1 2 1
link 1 2 2
distance? 1 2
cut 1 2 1
link 1 2 2
distance? 1 2
cut 1 2 2
cut 1 2 2
link 3 3 2
cut 4 4 2
link 1 2 2
link 1 3 3
link 2 3 4
distance? 1 2
distance? 1 3
distance? 2 4
link 2 4 3
link 3 5 3
link 4 5 1
distance? 4 5
cut 1 2 2
link 4 5 5
distance? 1 5
cut 2 3 4
link 2 5 5
link 1 5 2
distance? 1 2
cut 4 5 5
distance? 1 2
cut 3 5 3
distance? 1 2
cut 2 5 5
distance? 1 2
distance? 4 5
link 3 5 2
distance? 1 3
distance? 4 3
link 4 6 3
link 2 6 1
distance? 2 6
distance? 2 5
link 5 6 2
distance? 1 6
distance? 2 3
cut 2 4 3
link 2 5 4
distance? 4 1
cut 4 6 3
distance? 4 1
ok
ok
1
ok
ok
2
ok
ok
failed
failed
ok
ok
ok
2
3
-1
ok
ok
failed
10
ok
ok
6
ok
ok
ok
7
ok
7
ok
7
ok
-1
-1
ok
3
-1
ok
ok
1
-1
ok
4
5
ok
ok
7
ok
-1
数据范围
,。有关边权的中间计算保证不超出有符号 位整数范围。
题目来源为 VFleaKing。