有一天,wangyisong1996到森林里游玩,回来之后跟VFleaKing说,我发现好多棵会动的树耶!VFleaKing说,这有什么好稀奇的,我用手指头就能维护每棵树的形态。
于是又过了几天wangyisong1996到沙漠里游玩,回来之后跟VFleaKing说,我发现好多棵会动的仙人掌耶!VFleaKing说,这有什么好稀奇的,我用脚丫子就能维护每棵仙人掌的形态。
于是wangyisong1996很郁闷,他向你求助,请帮帮他吧。
如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。
如果一个无向图的每个连通块都是个仙人掌,且不存在自环,我们就称之为沙漠。
为了证明你确实能够维护仙人掌,我们给你
初始时没有任何边,且每个结点
- link
:在结点 间连一条权值为 的边。 且 为正整数。- 如果连边完成后图仍为沙漠,则输出 "ok"(不含引号)。
- 否则操作非法,撤销此次操作并输出 "failed"(不含引号)。
- cut
:在结点 间删掉一条权值为 的边。 且 为正整数。- 如果存在这样的边则输出 "ok"(不含引号)(如果有多条权值为
的边删去任意一条)。 - 否则操作非法,不进行操作并输出 "failed"(不含引号)。
- query1
:查询结点 到结点 的最短路信息。 。- 输出两个用空格隔开的整数
,分别代表最短路上点权的最小值、和。 - 如果没有路可到达则
。 - 如果最短路不唯一则
。
- query2
:查询以结点 为根,子仙人掌 的信息。 。- 以结点
为根,子仙人掌 的定义是,删掉 到 之间的所有简单路径上的边之后, 所在的连通块。 - 输出两个用空格隔开的整数
,分别代表子仙人掌 中点权的最小值、和。 - 如果
不连通则 。
- add1
:把结点 到结点 的最短路上的每一个结点的权值都加上 。 且 为正整数。- 如果有路可到达且最短路唯一,则输出 "ok"(不含引号)
- 否则操作非法,不进行操作并输出 "failed"(不含引号)。
- add2
:把以结点 为根,子仙人掌 的每一个结点的权值都加上 。 且 为正整数。- 如果
在同一个连通块里,则输出 "ok"(不含引号) - 否则操作非法,不进行操作并输出 "failed"(不含引号)。
输入格式
第一行两个用空格隔开的正整数
接下来一行
接下来
输出格式
对于每个操作,输出相应的结果。
样例一
input
11 23 10 5 11 7 8 14 30 3 16 20 19 link 1 2 5 link 2 3 3 link 3 4 7 link 4 5 8 link 2 6 10 link 6 7 15 link 4 7 3 link 6 8 9 link 6 8 6 link 7 9 12 link 9 11 10 link 7 10 4 link 9 10 8 query1 6 11 query1 2 10 query2 8 7 add1 8 5 100 query1 1 7 query2 8 7 add2 11 7 1000 query1 8 3 add2 3 2 2333 query1 1 5
output
ok ok ok ok ok ok ok ok ok ok ok ok ok -2 -2 5 73 16 85 ok 5 263 16 185 ok 1005 4233 ok 1011 9907
样例二
见样例数据下载。
限制与约定
保证 link 和 cut 操作中的
保证初始的
时间限制:
空间限制: