暂无测试数据。

DD 现在要出门散步，先给定一张 $n$ 个点 $m$ 条边的无向图，每条边有一个拥挤值，DD 会出门很多次，第 $i$ 次行走是从 $s_i$ 到 $t_i$，我们定义每条路径的不愉快值是这条路径上最大的拥挤值，现在 DD 想知道，她每次出门会产生的不愉快值最小是多少(如果起点终点不连通输出 $-1$ )

输入格式

第一行三个整数分别表示 $n,m,q$

接下来 $m$ 行，每行三个整数分别表示 $u_i,v_i,w_i$

接下来 $q$ 行，每行两个整数分别表示 $s_i,t_i$

输出格式

对于每次询问回答当前不愉快值最小是多少

数据范围

对于 $30\%$ 的数据，$n \leq 500,m,q \leq 1000$

对于另外 $20\%$ 的数据，$m=n-1$，且保证形成一棵树

对于 $100\%$ 的数据，$n \leq 50000,m \leq 200000,q \leq 100000$ ，拥挤值 $ \leq 10^9$

5 7 2
1 2 1
2 3 2
3 4 10
4 5 20
1 4 5
2 5 6
2 4 4
3 5
1 4

6
4