有一天，VFleaKing到森林里游玩，回来之后跟pyx1997说，我发现好多棵会动的树耶！pyx1997说，这有什么好稀奇的，我用手指头就能维护每棵树的形态。

于是又过了几天VFleaKing到沙漠里游玩，回来之后跟pyx1997说，我发现好多棵会动的仙人掌耶！pyx1997说，这有什么好稀奇的，我用脚丫子就能维护每棵仙人掌的形态。

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

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

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

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

1. link $v$ $u$ $w$：在结点 $v, u$ 间连一条权值为 $w$ 的边。
   • $1 \leq v, u \leq n$ 且 $w$ 为正整数。
   • 如果连边完成后图仍为沙漠，则输出 "ok"（不含引号）。
   • 否则操作非法，撤销此次操作并输出 "failed"（不含引号）。
2. cut $v$ $u$ $w$：在结点 $v, u$ 间删掉一条权值为 $w$ 的边。
   • $1 \leq v, u \leq n$ 且 $w$ 为正整数。
   • 如果存在这样的边则输出 "ok"（不含引号）（如果有多条权值为 $w$ 的边删去任意一条）。
   • 否则操作非法，不进行操作并输出 "failed"（不含引号）。
3. distance? $v$ $u$：查询结点 $v$ 到结点 $u$ 的最短路信息。
   • $1 \leq v, u \leq n$。
   • 输出两个用空格隔开的整数 $l_m, w_m$。
   • $l_m$ 代表最短路的长度，$w_m$ 代表最短路上的边权的最小值。
   • 如果 $v = u$ 则 $l_m = 0, w_m = 2147483647$。
   • 如果没有路可到达则 $l_m = -1, w_m = -1$。
   • 如果最短路不唯一则 $w_m = -1$。

输入格式

第一行两个用空格隔开的正整数 $n, m$ 表示一共有 $n$ 个结点，$m$ 个操作。

接下来 $m$ 行，每行代表一个操作。

输出格式

对于每个操作，输出相应的结果。

样例一

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 -1
ok
ok
ok
-1 -1
ok
ok
ok
ok
ok
ok
11 1
10 2
11 1
11 2
ok
1 1
ok
ok
ok

样例二

见样例数据下载，这组超良心数据中包含了许多你需要考虑的细节。

样例三

见样例数据下载

限制与约定

$1 \leq n \leq 100000, 1 \leq m \leq 400000$。

保证 link 和 cut 操作中的 $w$ 满足 $1 \leq w \leq 10000$，所以关于边权的计算不会超出 32 位有符号整数范围。

时间限制：$5\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载