有一天,VFleaKing到森林里游玩,回来之后跟pyx1997说,我发现好多棵会动的树耶! pyx1997说,这有什么好稀奇的,我用手指头就能维护每棵树的形态。 于是又过了几天VFleaKing到沙漠里游玩,回来之后跟pyx1997说,我发现好多棵会动的仙人掌耶! pyx1997说,这有什么好稀奇的,我用脚丫子就能维护每棵仙人掌的形态。 于是VFleaKing很郁闷,他向你求助,请帮帮他吧。 如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。 如果一个无向图的每个连通块都是个仙人掌,且不存在自环,我们就称之为沙漠。 为了证明你确实能够维护仙人掌,我们给你n个结点,从1到n标号。初始时没有任何边。每次进行如下操作之一:
第一行两个用空格隔开的正整数n, m表示一共有n个结点,m个操作。 接下来m行,每行代表一个操作。
对于每个操作,输出相应的结果。
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 <= 100000
1 <= m <= 500000
保证中间有关边权的计算不会超过int范围。(祝pascal选手早日转C++,其实我在说longint)