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