Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Cities Excursions

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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.

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.

Example

Input

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

Output

2

-1

-1

2

-1

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/19/2018 15:47:23 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|