说明

给定一个包含 $n$个节点和 $m$条边的图，每条边有一个权值。

你的任务是回答 $k$个询问，每个询问包含两个正整数 $s$和 $t$表示起点和终点，要求寻找从 $s$到 $t$的一条路径，使得路径上权值最大的一条边权值最小。

输入格式

第一行包含三个整数 $n, m, k$，分别表示 $n$个节点，$m$条路径，$k$个询问。

接下来 $m$行，每行三个整数 $u, v, w$，表示一个由 $u$到 $v$的长度为 $w$的双向边。

再接下来 $k$行，每行两个整数 $s, t$，表示询问从 $s$连接到 $t$的所有路径中单边长度最大值的最小值。

输出格式

输出包含 $k$行，每一行包含一个整数 $p$。$p$表示 $s$连接到 $t$的所有路径中单边长度最大值的最小值。另外，如果 $s$到 $t$没有路径相连通，输出-1即可。

样例

8 11 3
1 2 10
2 5 50
3 4 60
7 5 60
3 6 30
1 5 30
6 7 20
1 7 70
2 3 20
3 5 40
2 6 90
1 7
2 8
6 2

30
-1
30

提示

对于 $$的数据 $n \le 100$，$m \le 1000$，$k \le 100$，$w \le 1000$。

对于 $$的数据 $n \le 1000$，$m \le 10000$，$k \le 1000$，$w \le 100000$。

对于 $$的数据 $n \le 1000$，$m \le 100000$，$k \le 1000$，$w \le 10000000$。

本题可能会有重边，所有的 $w$均不相同。