Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only 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-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/05/2020 23:30:48 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|