Description

给定一个 $n$ 点 $m$ 边的边带权无向图。

$q$ 次询问 $u$ 和 $v$ 之间路径上权值最大值最小是多少。

若 $u,v$ 不连通，输出 -1。

Input Format

第一行三个个整数 $n,m,q$ 分别表示节点个数，边数，询问次数。

接下来 $m$ 行，每行三个整数 $u,v,w$ 表示一条边的两个顶点和边权。

接下来 $q$ 行，每行两个整数 $u,v$ 表示询问。

Output Format

共 $q$ 行，每行一个整数表示询问结果。

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

Hint

$1≤n,q≤10^3,1≤m≤10^5,1≤w≤10^9$

Source

模板