← 返回题目列表

Codeforces · 864/F

F. 城市游览

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

Berland 有 n 个城市。其中一些对与 m 个有向道路相连。人们只能使用这些道路从一个城市移动到另一个城市。没有道路将城市与其本身连接起来。对于每对城市 (x, y),从 x 到 y 至多有一条道路。

从城市 s 到城市 t 的路径是城市 p1, p2, ... , pk 的序列,其中 p1 = s, pk = t,对于从 1 到 k - 1 的每个 i,都有一条从城市 pi 到城市 pi + 1 的道路。该路径可以多次经过除 t 之外的每个城市。它不能多次通过 t。

如果从 s 到 t 的路径 p 是字典顺序上最小的路径,则该路径 p 是理想的。换句话说,如果对于从 s 到 t 的任何其他路径 q pi < qi,则 p 是从 s 到 t 的理想路径,其中 i 是使得 pi ≠ qi 的最小整数。

该国有一家旅行社提供 q 个不寻常的旅行:第 j 个旅行从城市 sj 开始,到城市 tj 结束。

对于每对 sj, tj 帮助机构研究从 sj 到 tj 的理想路径。请注意,从 sj 到 tj 可能不存在理想路径。这是可能的,有两个原因:

- 没有从 sj 到 tj 的路径;
- 存在从 sj 到 tj 的路径,但对于每个这样的路径 p 都有另一条从 sj 到 tj 的路径 q,使得 pi > qi,其中 i 是 pi ≠ qi 的最小整数。

该机构想知道从 sj 到 tj 的理想路径以及该路径中的第 kj 个城市(在从 sj 到 tj 的途中)。

对于每个三元组 sj, tj, kj (1 ≤ j ≤ q) 查找是否存在从 sj 到 tj 的理想路径,并打印该路径中的第 kj 个城市(如果有)。

输入

第一行包含三个整数 n、m 和 q (2 ≤ n ≤ 3000,0 ≤ m ≤ 3000, 1 ≤ q ≤ 4·105) — 城市数量、道路数量和游览次数。

接下来的m行每行包含两个整数xi和yi(1≤xi,yi≤n,xi≠yi),表示第i条路从城市xi到城市yi。所有道路都是单向的。两个城市之间每个方向不能有多于一条道路。

接下来的 q 行包含三个整数 sj、tj 和 kj (1 ≤ sj, tj ≤ n, sj ≠ tj, 1 ≤ kj ≤ 3000)。

输出

在第 j 行中打印从 sj 到 tj 的理想路径中第 kj 个城市。如果从 sj 到 tj 不存在理想路径,或者整数 kj 大于该路径的长度,则在第 j 行打印字符串“-1”(不带引号)。

示例

输入 #1

7 7 5
1 2
2 3
1 3
3 4
4 5
5 3
4 6
1 4 2
2 6 1
1 7 3
1 3 2
1 3 5

输出 #1

2
-1
-1
2
-1