← 返回题目列表

Codeforces · 687/D

D. 分裂王国 II

中文机器翻译题面 查看原题

很久以前,有一个伟大的王国,由伟大的艾莉亚和帕里大帝统治。这两个人对自己喜欢的数字有些疑问,所以他们决定瓜分这个伟大的王国。

这个伟大的王国由编号为 1 到 n 的 n 个城市以及这些城市之间编号为 1 到 m 的 m 条双向道路组成。第 i 条路的长度等于 wi。大雅利安和帕里大帝正在讨论破坏一些道路的前缀(所有数字小于某个x的道路)和后缀(所有数字大于某个x的道路),这样就只剩下数字为l,l + 1,...,r - 1和r的道路。

之后他们会将这个伟大的王国分成两块(每个城市都属于一块),这样划分的难度就会降到最低。分区的硬度是指其两个端点位于王国同一部分的道路的最大长度。如果没有这样的道路,则划分的硬度被认为等于-1。

历史学家找到了伟大王国的地图,他们对那些伟大统治者选择的l和r有q个猜测。给定这些数据,对于每个猜测 li 和 ri 都会打印王国划分的最小可能硬度。

输入

输入的第一行包含三个整数 n、m 和 q (1 ≤ n, q ≤ 1000, $$1 \leq m \leq \frac{n \times (n-1)}{2}$$) – 分别是大王国中的城市和道路的数量以及猜测的数量。

接下来 m 行中的第 i 行包含三个整数 ui、vi 和 wi (1 ≤ ui, vi ≤ n, 0 ≤ wi ≤ 109),表示连接城市 ui 和 vi 的道路编号 i,其长度等于 wi。保证没有道路将城市与其本身连接起来,并且没有一对城市由多条道路连接。

接下来的 q 行中的每一行都包含一对整数 li 和 ri (1 ≤ li ≤ ri ≤ m)——历史学家对王国中剩余道路的猜测。

输出

对于每个猜测,打印所描述场景中划分的最小可能硬度。

示例

输入 #1

5 6 5
5 4 86
5 1 0
1 3 38
2 1 33
2 4 28
2 3 40
3 5
2 6
1 3
2 3
1 6

输出 #1

-1
33
-1
-1
33