3465. 动态仙人掌 II
#3465. 动态仙人掌 II
题目描述
有一天，VFleaKing到森林里游玩，回来之后跟pyx1997说，我发现好多棵会动的树耶！
pyx1997说，这有什么好稀奇的，我用手指头就能维护每棵树的形态。
于是又过了几天VFleaKing到沙漠里游玩，回来之后跟pyx1997说，我发现好多棵会动的仙人掌耶！
pyx1997说，这有什么好稀奇的，我用脚丫子就能维护每棵仙人掌的形态。
于是VFleaKing很郁闷，他向你求助，请帮帮他吧。
如果一个无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。
如果一个无向图的每个连通块都是个仙人掌，且不存在自环，我们就称之为沙漠。
为了证明你确实能够维护仙人掌，我们给你n个结点，从1到n标号。初始时没有任何边。每次进行如下操作之一：
1. link v u w
在结点v, u间连一条权值为w的边。1 <= v, u <= n且w为正整数。
如果连边完成后图仍为沙漠，则输出"ok"（不含引号）。
否则操作非法，撤销此次操作并输出"failed"（不含引号）。
2. cut v u w 在结点v, u间删掉权值为w的边。1 <= v, u <= n且w为正整数。
如果存在这样的边则输出"ok"（不含引号）（如果有多条权值为w的边删去任意一条）。
否则操作非法，不进行操作并输出"failed"（不含引号）。
3. distance? v u 查询结点v到结点u的最短路信息。1 <= v, u <= n。
输出两个用空格隔开的整数Lm, Wm。
Lm代表最短路的长度，Wm代表最短路上的边权的最小值。
如果v = u则Lm = 0, Wm = 2147483647。
如果没有路可到达则Lm = -1, Wm = -1。
如果最短路不唯一则Wm = -1。
输入格式
第一行两个用空格隔开的正整数n, m表示一共有n个结点，m个操作。
接下来m行，每行代表一个操作。
输出格式
对于每个操作，输出相应的结果。
样例
样例输入
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 1
ok
ok
2 -1
ok
ok
failed
failed
ok
ok
ok
2 2
3 3
-1 -1
ok
ok
failed
10 3
ok
ok
6 3
ok
ok
ok
7 2
ok
7 2
ok
7 2
ok
-1 -1
-1 -1
ok
3 3
-1 -1
ok
ok
1 1
-1 -1
ok
4 2
5 1
ok
ok
7 2
ok
-1 -1
数据范围与提示
1 <= n <= 100000
1 <= m <= 400000
保证中间有关边权的计算不会超过int范围。（祝pascal选手早日转C++，其实我在说longint）