题目描述
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 的正整数。