题目描述

一张图有 $n$ 个点， $m$ 条有向边。无自环。

定义从 $s$ 到 $t$ 的路径为一个顶点序列 $[p_1,p_2,...,p_l]$ ，其中 $p_1 = s, p_l = t$，并且对于任意的 $1 \le i < l$，都存在一条从 $p_i$ 到 $p_{i + 1}$ 的有向边。

对于两个点 $s,t$，我们称所有从 $s$ 到 $t$ 的所有路径中字典序最小的路径为由 $s$ 到 $t$ 的理想路径。

对于两个点 $s,t$ ，可能不存在理想路径。原因有两种：

1. $s$ 无法到达 $t$ ；
2. 有很多条从 $s$ 到 $t$ 的路径，并且对于任意一条路径都有存在一条字典序比其字典序更小的路径。

我们想要知道从 $s$ 出发，到达 $t$ 的理想路径中经过的第 $k$ 个点的编号是什么。

一共有 $q$ 组这样的询问。

输入格式

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

接下来 $m$ 行，每行两个正整数 $x_i,y_i$，表示第 $i$ 条边是从 $x_i$ 到 $y_i$ 的有向边。

接下来 $q$ 行，每行三个正整数 $s,t,k$ ，表示一组询问。

输出格式

对于每组询问输出一行表示答案。

如果从 $s$ 到 $t$ 没有理想路径，或者 $s$ 到 $t$ 的理想路径经过的点数小于 $k$ ，那么输出 $-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

样例输出

2
-1
-1
2
-1

数据规模与约定

$x_i,y_i,s,t \le N,x_i \not = y_i,k \le 2000$，同一组询问中 $s \not= t$。