UOJ Logo

NOI.AC

#55. treelink

统计

题目描述

D 国有 $n$ 个城市,有若干条道路,每条道路能连接两个城市,并且有一定的长度。

可是……初始时,并没有任何道路存在。接下来,有 $q$ 个操作需要你依次完成:

  • $x$ $y$ 表示:询问城市 $x$ 与 $y$ 之间的最短路径长度;如果不存在任何路径,则你应当回答-1。
  • $x$ $y$ $w$ 表示:在城市 $x$ 与 $y$ 之间修建了一条长度为 $w$ 的道路。保证在此之前在城市 $x$ 与 $y$ 之间不存在任何路径(即:假如在此之前给出一个 $x$ $y$ 的操作,保证其答案应当为-1)。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n, q$。

接下来 $q$ 行,每行输入两个或者三个正整数,形如 $x$ $y$ 或 $x$ $y$ $w$,表示一个操作。

每行中,相邻的两个数之间用一个空格隔开。

输出格式

输出到标准输出。

对于每个形如 $x$ $y$ 的操作,你需要输出一行,包含一个整数,为你对于这次询问的答案。

样例

输入

4 7
1 3
1 3 100
2 3 200
1 3
1 2
2 3
1 4

输出

-1
100
300
200
-1

解释

TODO

数据规模

对于测试点1,2,保证 $n, q \leq 200$。

对于测试点1,2,3,4,保证 $n, q \leq 2000$。

对于测试点1,2,3,4,5,6,保证 $n, q \leq 100,000$。

编号为奇数的测试点满足:所有形如 $x$ $y$ $w$ 的询问都出现在所有形如 $x$ $y$ 的询问之后。

对于所有数据,保证 $1 \leq n, q \leq 500,000$。所有的 $w$ 均为不超过 1000 的正整数。