# #P864F. Cities Excursions

# Cities Excursions

## Description

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.

The first line contains three integers *n*, *m* and *q* (2 ≤ *n* ≤ 3000,0 ≤ *m* ≤ 3000, 1 ≤ *q* ≤ 4·10^{5}) — 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).

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.

## Input

The first line contains three integers *n*, *m* and *q* (2 ≤ *n* ≤ 3000,0 ≤ *m* ≤ 3000, 1 ≤ *q* ≤ 4·10^{5}) — 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).

## Output

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.

## Samples

```
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
```