题目描述

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 的正整数。