#P3464. 动态仙人掌 I

动态仙人掌 I

动态仙人掌 I

题目描述

VFleaKing 去森林看见了会动的树,在沙漠看见了会动的仙人掌。pyx1997 说他会维护它们的形态,VFleaKing 想请你也试一试。

如果一个无向连通图的每条边至多属于一个简单环,就称它为仙人掌。如果无向图的每个连通分量都是仙人掌,并且图中没有自环,就称它为沙漠。允许两点之间有平行边,两条平行边可以组成一个环。

给定 nn 个编号为 11 到 nn 的节点,初始时没有边。依次处理以下操作。

  • link v u w 尝试在 v,uv,u 之间加入一条权值为 ww的边。如果加入后仍是沙漠,则保留新边并输出 ok,否则撤销新增边并输出 failed。
  • cut v u w 删除 v,uv,u 之间满足给定权值的一条边。若有多条符合的边,任选一条删除。删除成功输出 ok,否则不做修改并输出 failed。
  • distance? v u 查询 vv 到 uu 的最短路长度,要求 v≠uv\ne u。若两点不连通,输出 -1。

输入格式

第一行包含两个正整数 n,mn,m,分别表示节点数和操作数。

接下来 mm 行,每行给出一个操作。节点编号 v,uv,u 都在 11 到 nn 之间,ww 为正整数。

输出格式

对每次操作按照上述规则输出一行。

样例 #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

数据范围

1≤n≤1000001\le n\le 100000,1≤m≤4000001\le m\le 400000。有关边权的中间计算保证不超出有符号 3232 位整数范围。

题目来源为 VFleaKing。