CF864F.Cities Excursions

There are n cities in Berland. Some pairs of them are connected with m directed roads. One can use only these roads to move from one city to another. There are no roads that connect a city to itself. For each pair of cities (x, y) there is at most one road from x to y.

A path from city s to city t is a sequence of cities _p_1, _p_2, ... , p__k, where _p_1 = s, p__k = t, and there is a road from city p__i to city p__i + 1 for each i from 1 to k - 1. The path can pass multiple times through each city except t. It can't pass through t more than once.

A path p from s to t is ideal if it is the lexicographically minimal such path. In other words, p is ideal path from s to t if for any other path q from s to t p__i < q__i, where i is the minimum integer such that p__i ≠ q__i.

There is a tourist agency in the country that offers q unusual excursions: the j-th excursion starts at city s__j and ends in city t__j.

For each pair s__j, t__j help the agency to study the ideal path from s__j to t__j. Note that it is possible that there is no ideal path from s__j to t__j. This is possible due to two reasons:

• there is no path from s__j to t__j;
• there are paths from s__j to t__j, but for every such path p there is another path q from s__j to t__j, such that p__i > q__i, where i is the minimum integer for which p__i ≠ q__i.

The agency would like to know for the ideal path from s__j to t__j the k__j-th city in that path (on the way from s__j to t__j).

For each triple s__j, t__j, k__j (1 ≤ j ≤ q) find if there is an ideal path from s__j to t__j and print the k__j-th city in that path, if there is any.

伯兰德有 $n$ 座城市。其中某些城市对之间由 $m$ 条有向道路连接。人们只能通过这些道路在城市间移动。不存在连接某城市到其自身的道路。对于任意一对城市 $(x, y)$，至多只存在一条从 $x$ 到 $y$ 的道路。

从城市 $s$ 到城市 $t$ 的一条路径是一个城市序列 $p_1, p_2, \dots, p_k$，满足 $p_1 = s$、$p_k = t$，且对每个 $i = 1, 2, \dots, k-1$，均存在一条从城市 $p_i$ 到城市 $p_{i+1}$ 的道路。该路径可多次经过除 $t$ 外的任意城市，但不能多次经过 $t$（即 $t$ 在路径中至多出现一次）。

从 $s$ 到 $t$ 的路径 $p$ 被称为理想路径，当且仅当它是所有从 $s$ 到 $t$ 的路径中字典序最小者。换言之，若 $p$ 是从 $s$ 到 $t$ 的理想路径，则对任意另一条从 $s$ 到 $t$ 的路径 $q$，设 $i$ 是满足 $p_i \ne q_i$ 的最小下标，则必有 $p_i < q_i$。

该国有一家旅游机构，提供 $q$ 种特殊游览路线：第 $j$ 种游览路线起始于城市 $s_j$，终止于城市 $t_j$。

对每一对 $(s_j, t_j)$，请协助该机构找出从 $s_j$ 到 $t_j$ 的理想路径。注意：从 $s_j$ 到 $t_j$ 可能不存在理想路径，原因如下两种之一：

• 不存在从 $s_j$ 到 $t_j$ 的路径；
• 存在从 $s_j$ 到 $t_j$ 的路径，但对任意一条这样的路径 $p$，总存在另一条从 $s_j$ 到 $t_j$ 的路径 $q$，使得 $p_i > q_i$，其中 $i$ 是满足 $p_i \ne q_i$ 的最小下标。

该机构希望知道：在从 $s_j$ 到 $t_j$ 的理想路径中（若存在），第 $k_j$ 个城市是哪一个（按从 $s_j$ 到 $t_j$ 的顺序计数）。

对每个三元组 $(s_j, t_j, k_j)$（其中 $1 \le j \le q$），请判断是否存在从 $s_j$ 到 $t_j$ 的理想路径；若存在，则输出该路径中第 $k_j$ 个城市；否则不输出任何内容。

The first line contains three integers n, m and q (2 ≤ n ≤ 3000,0 ≤ m ≤ 3000, 1 ≤ q ≤ 4·105) — the number of cities, the number of roads and the number of excursions.

Each of the next m lines contains two integers x__i and y__i (1 ≤ x__i, y__i ≤ n, x__i ≠ y__i), denoting that the i-th road goes from city x__i to city y__i. All roads are one-directional. There can't be more than one road in each direction between two cities.

Each of the next q lines contains three integers s__j, t__j and k__j (1 ≤ s__j, t__j ≤ n, s__j ≠ t__j, 1 ≤ k__j ≤ 3000).

第一行包含三个整数 $n$、$m$ 和 $q$（$2 \leq n \leq 3000$，$0 \leq m \leq 3000$，$1 \leq q \leq 4\cdot10^5$）——分别表示城市的数量、道路的数量以及远足活动的数量。

接下来的 $m$ 行中，每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq n$，$x_i \neq y_i$），表示第 $i$ 条道路从城市 $x_i$ 指向城市 $y_i$。所有道路均为单向。任意两个城市之间在每个方向上至多只有一条道路。

接下来的 $q$ 行中，每行包含三个整数 $s_j$、$t_j$ 和 $k_j$（$1 \leq s_j, t_j \leq n$，$s_j \neq t_j$，$1 \leq k_j \leq 3000$）。

In the j-th line print the city that is the k__j-th in the ideal path from s__j to t__j. If there is no ideal path from s__j to t__j, or the integer k__j is greater than the length of this path, print the string '-1' (without quotes) in the j-th line.

在第 $j$ 行输出从 $s_j$ 到 $t_j$ 的理想路径中第 $k_j$ 个城市。若从 $s_j$ 到 $t_j$ 不存在理想路径，或整数 $k_j$ 大于该路径的长度，则在第 $j$ 行输出字符串 -1（不带引号）。