UOJ Logo

NOI.AC

2S 512MB

#14. A

统计

小w负责a国的火车系统调度。a国的火车系统由$m$条铁轨构成,每条火车线路形如$(a,b,c)$的形式,表示有两辆火车在$c$时刻,分别从$a$地和$b$地出发前往对面。由于a国科技发达,我们可以认为火车不需要时间,在$c$时刻出发就可以在$c$时刻到达。

为了从$x$到$y$,小w可能会换乘一系列的铁路线路,小w为了从第一个铁路线路$(a1, b1, c1)$换乘第二个铁路线路$(a2, b2, c2)$,需要$c1 \leq c2, b1 = a2$。

现在有$q$个询问,每个询问问小w最早什么时间能从$a$地到$b$地。注意一条换乘线路的时间是线路上最后一段火车的到达时间。

输入格式

第一行三个整数$n, m, q$。

接下来$m$行,每行三个整数$a_i, b_i, c_i$。

最后$q$行,每行表示一个询问$a_i, b_i$, $a_i \not= b_i$。

输出格式

$q$行,每行一个整数表示答案。

如果不能到达输出-1.

样例一

input

3 3 3
1 3 1
2 3 2
1 2 1
1 2
1 3
2 3

output

1
1
1

样例二

input

3 3 3
1 3 5
2 3 2
1 2 7
1 2
1 3
2 3

output

7
5
2

数据范围

时间限制1s, 空间范围512MB

$q \leq 10^5$

测试点编号 $n$的规模 $m, c_i$的规模
1,2$n \leq 20$$m \leq n^2, c_i \leq 10^9$
3,4$n \leq 500$$m \leq n^2, c_i \leq 10^9$
5,6$n \leq 3000$$m \leq 5 \times 10^5, c_i \leq 100$
7,8,9,10$n \leq 3000$$m \leq 5 \times 10^5, c_i \leq 10^9$