有一天,VFleaKing到森林里游玩,回来之后跟pyx1997说,我发现好多棵会动的树耶!pyx1997说,这有什么好稀奇的,我用手指头就能维护每棵树的形态。
于是又过了几天VFleaKing到沙漠里游玩,回来之后跟pyx1997说,我发现好多棵会动的仙人掌耶!pyx1997说,这有什么好稀奇的,我用脚丫子就能维护每棵仙人掌的形态。
于是VFleaKing很郁闷,他向你求助,请帮帮他吧。
如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。
如果一个无向图的每个连通块都是个仙人掌,且不存在自环,我们就称之为沙漠。
为了证明你确实能够维护仙人掌,我们给你
- link
:在结点 间连一条权值为 的边。 且 为正整数。- 如果连边完成后图仍为沙漠,则输出 "ok"(不含引号)。
- 否则操作非法,撤销此次操作并输出 "failed"(不含引号)。
- cut
:在结点 间删掉一条权值为 的边。 且 为正整数。- 如果存在这样的边则输出 "ok"(不含引号)(如果有多条权值为
的边删去任意一条)。 - 否则操作非法,不进行操作并输出 "failed"(不含引号)。
- distance?
:查询结点 到结点 的最短路信息。 。- 输出一个整数
。 代表最短路的长度。- 如果
则 。 - 如果没有路可到达则
。
输入格式
第一行两个用空格隔开的正整数
接下来
输出格式
对于每个操作,输出相应的结果。
样例一
input
7 20 distance? 4 5 link 3 4 9 link 2 4 6 cut 2 4 6 distance? 5 7 link 6 7 8 link 6 4 1 link 2 1 2 link 2 3 5 link 7 5 2 link 2 5 9 distance? 4 5 distance? 5 6 distance? 5 4 distance? 2 7 link 1 2 7 distance? 4 6 cut 3 4 9 link 4 5 4 link 2 3 7
output
-1 ok ok ok -1 ok ok ok ok ok ok 11 10 11 11 ok 1 ok ok ok
样例二
见样例数据下载,这组超良心数据中包含了许多你需要考虑的细节。
样例三
见样例数据下载
限制与约定
保证 link 和 cut 操作中的
时间限制:
空间限制: