#P3466. 动态仙人掌 III

动态仙人掌 III

动态仙人掌 III

题目描述

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

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

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

  • link v u wA wB 尝试在 v,uv,u 之间加入一条权值 AA 为 wA\mathrm{wA}、权值 BB 为 wB\mathrm{wB}的边。如果加入后仍是沙漠,则保留新边并输出 ok,否则撤销新增边并输出 failed。
  • cut v u wA wB 删除 v,uv,u 之间满足给定权值的一条边。若有多条符合的边,任选一条删除。删除成功输出 ok,否则不做修改并输出 failed。
  • distance? v u 按权值 AA 求最短路,输出两个整数 Lm,WmL_m,W_m。LmL_m 是最短路长度,WmW_m 是该最短路上的最小权值 BB。若有多条按 AA 计算的最短路,Wm=−1W_m=-1。若两点不连通,输出 -1 -1。若 v=uv=u,输出 0 2147483647。
  • add v u d 将 vv 到 uu 的唯一一条按 AA 计算的最短路上的每条边的权值 BB 增加 dd,权值 AA 不变。要求 v≠uv\ne u。若最短路存在且唯一,执行操作并输出 ok,否则不做修改并输出 failed。

输入格式

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

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

输出格式

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

样例 #1

6 56
link 1 2 1 3
link 1 2 2 5
distance? 1 2
cut 1 2 1 3
link 1 2 2 5
distance? 1 2
cut 1 2 2 5
link 1 2 2 4
add 1 2 1
cut 1 2 2 4
cut 1 2 2 5
link 3 3 2 2
cut 4 4 2 2
link 1 2 2 4
link 1 3 3 5
link 2 3 4 3
distance? 1 2
distance? 1 3
distance? 2 4
add 1 2 3
link 2 4 3 2
link 3 5 3 4
link 4 5 1 5
distance? 4 5
cut 1 2 2 7
link 4 5 5 4
distance? 1 5
cut 2 3 4 3
link 2 5 5 3
link 1 5 2 4
distance? 1 2
add 3 4 3
cut 4 5 5 7
distance? 1 2
cut 3 5 3 7
distance? 1 2
cut 2 5 5 4
cut 2 5 5 3
distance? 1 2
add 1 2 3
link 3 5 6 7
distance? 1 3
add 3 5 1
distance? 5 3
distance? 4 3
link 4 6 3 1
link 2 6 7 2
distance? 2 6
link 5 6 2 4
distance? 1 6
distance? 2 3
cut 2 4 3 2
link 2 5 4 3
distance? 4 1
cut 4 6 3 1
distance? 4 1
ok
ok
1 3
ok
ok
2 -1
ok
ok
failed
ok
ok
failed
failed
ok
ok
ok
2 4
3 5
-1 -1
ok
ok
ok
failed
10 2
ok
ok
6 4
ok
ok
ok
7 3
ok
ok
7 3
ok
7 3
failed
ok
-1 -1
failed
ok
3 5
ok
5 5
-1 -1
ok
ok
6 1
ok
4 4
13 1
ok
ok
7 1
ok
-1 -1

数据范围

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

题目来源为 VFleaKing。