动态仙人掌 II

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file bzoj_3465.in Output file bzoj_3465.out

【注意】

由于题目过于神犇(不对,是因为穷),我们没有测试数据……如果哪位犇写出来了请联系我们……

【题目描述】

有一天,VFleaKing到森林里游玩,回来之后跟pyx1997说,我发现好多棵会动的树耶!

pyx1997说,这有什么好稀奇的,我用手指头就能维护每棵树的形态。

于是又过了几天VFleaKing到沙漠里游玩,回来之后跟pyx1997说,我发现好多棵会动的仙人掌耶!

pyx1997说,这有什么好稀奇的,我用脚丫子就能维护每棵仙人掌的形态。

于是VFleaKing很郁闷,他向你求助,请帮帮他吧。

 

如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。

如果一个无向图的每个连通块都是个仙人掌,且不存在自环,我们就称之为沙漠。

 

为了证明你确实能够维护仙人掌,我们给你n个结点,从1n标号。初始时没有任何边。每次进行如下操作之一:

1. link v u w

    在结点v, u间连一条权值为w的边。1 <= v, u <= nw为正整数。

    如果连边完成后图仍为沙漠,则输出"ok"(不含引号)。

    否则操作非法,撤销此次操作并输出"failed"(不含引号)。

2. cut v u w 在结点v, u间删掉权值为w的边。1 <= v, u <= nw为正整数。

    如果存在这样的边则输出"ok"(不含引号)(如果有多条权值为w的边删去任意一条)。

    否则操作非法,不进行操作并输出"failed"(不含引号)。

3. distance? v u 查询结点v到结点u的最短路信息。1 <= v, u <= n, v != u

    输出两个用空格隔开的整数Lm, Wm

    Lm代表最短路的长度,Wm代表最短路上的边权的最小值。

    如果没有路可到达则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)


【来源】

【题目来源】

耒阳大世界(衡阳八中) OJ 3465