#2820. 动态仙人掌 I

动态仙人掌 I

Description

有一天,VFleaKing到森林里游玩,回来之后跟pyx1997说,我发现好多棵会动的树耶! pyx1997说,这有什么好稀奇的,我用手指头就能维护每棵树的形态。 于是又过了几天VFleaKing到沙漠里游玩,回来之后跟pyx1997说,我发现好多棵会动的仙人掌耶! pyx1997说,这有什么好稀奇的,我用脚丫子就能维护每棵仙人掌的形态。 于是VFleaKing很郁闷,他向你求助,请帮帮他吧。

如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。 如果一个无向图的每个连通块都是个仙人掌,且不存在自环,我们就称之为沙漠。

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

  1. link v u w 在结点v, u间连一条权值为w的边。1 <= v, u <= n且w为正整数。 如果连边完成后图仍为沙漠,则输出"ok"(不含引号)。 否则操作非法,撤销此次操作并输出"failed"(不含引号)。
  2. cut v u w 在结点v, u间删掉权值为w的边。1 <= v, u <= n且w为正整数。 如果存在这样的边则输出"ok"(不含引号)(如果有多条权值为w的边删去任意一条)。 否则操作非法,不进行操作并输出"failed"(不含引号)。
  3. distance? v u 查询结点v到结点u的最短路信息。1 <= v, u <= n。 输出一个整数Lm。 Lm代表最短路的长度。 如果v = u则Lm = 0。 如果没有路可到达则Lm = -1。

Format

Input

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

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

Output

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

Samples

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

ok

ok

2

ok

ok

failed

failed

ok

ok

ok

2

3

-1

ok

ok

failed

10

ok

ok

6

ok

ok

ok

7

ok

7

ok

7

ok

-1

-1

ok

3

-1

ok

ok

1

-1

ok

4

5

ok

ok

7

ok

-1

Limitation

1 <= n <= 100000

1 <= m <= 400000

保证中间有关边权的计算不会超过int范围。(祝pascal选手早日转C++,其实我在说longint)