English · Original
Chinese · Translation
Formal · Original
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.
## Input
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).
## 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]
Berland 有 #cf_span[n] 座城市。某些城市对之间由 #cf_span[m] 条有向道路连接。人们只能通过这些道路从一座城市移动到另一座城市。不存在连接城市到自身的道路。对于每对城市 #cf_span[(x, y)]，从 #cf_span[x] 到 #cf_span[y] 的道路至多有一条。
从城市 #cf_span[s] 到城市 #cf_span[t] 的路径是一系列城市 #cf_span[p1], #cf_span[p2], ... , #cf_span[pk]，其中 #cf_span[p1 = s]，#cf_span[pk = t]，且对于每个 #cf_span[i] 从 #cf_span[1] 到 #cf_span[k - 1]，都存在一条从城市 #cf_span[pi] 到城市 #cf_span[pi + 1] 的道路。该路径可以多次经过每个城市，但除了 #cf_span[t] 外，不能经过 #cf_span[t] 超过一次。
从 #cf_span[s] 到 #cf_span[t] 的路径 #cf_span[p] 被称为 _理想路径_，如果它是字典序最小的此类路径。换句话说，#cf_span[p] 是从 #cf_span[s] 到 #cf_span[t] 的理想路径，当且仅当对于任何其他从 #cf_span[s] 到 #cf_span[t] 的路径 #cf_span[q]，都有 #cf_span[pi < qi]，其中 #cf_span[i] 是满足 #cf_span[pi ≠ qi] 的最小整数。
该国有一家旅游公司提供 #cf_span[q] 项不寻常的观光行程：第 #cf_span[j] 项行程从城市 #cf_span[sj] 开始，到城市 #cf_span[tj] 结束。
对于每对 #cf_span[sj], #cf_span[tj]，请帮助该公司研究从 #cf_span[sj] 到 #cf_span[tj] 的理想路径。注意，从 #cf_span[sj] 到 #cf_span[tj] 可能不存在理想路径，原因有两个：
该公司希望知道从 #cf_span[sj] 到 #cf_span[tj] 的理想路径中第 #cf_span[kj] 座城市（从 #cf_span[sj] 到 #cf_span[tj] 的路径上）。
对于每个三元组 #cf_span[sj], #cf_span[tj], #cf_span[kj]（#cf_span[1 ≤ j ≤ q]），请判断是否存在从 #cf_span[sj] 到 #cf_span[tj] 的理想路径，若存在，请输出该路径中的第 #cf_span[kj] 座城市。
第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[q]（#cf_span[2 ≤ n ≤ 3000]，#cf_span[0 ≤ m ≤ 3000]，#cf_span[1 ≤ q ≤ 4·105]）——分别表示城市数量、道路数量和观光行程数量。
接下来的 #cf_span[m] 行每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi, yi ≤ n]，#cf_span[xi ≠ yi]），表示第 #cf_span[i] 条道路从城市 #cf_span[xi] 指向城市 #cf_span[yi]。所有道路均为单向，任意两座城市之间在每个方向上至多有一条道路。
接下来的 #cf_span[q] 行每行包含三个整数 #cf_span[sj], #cf_span[tj] 和 #cf_span[kj]（#cf_span[1 ≤ sj, tj ≤ n]，#cf_span[sj ≠ tj]，#cf_span[1 ≤ kj ≤ 3000]）。
在第 #cf_span[j] 行，输出从 #cf_span[sj] 到 #cf_span[tj] 的理想路径中的第 #cf_span[kj] 座城市。如果从 #cf_span[sj] 到 #cf_span[tj] 不存在理想路径，或者 #cf_span[kj] 大于该路径的长度，请在第 #cf_span[j] 行输出字符串 '_-1_'（不含引号）。
## Input
第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[q]（#cf_span[2 ≤ n ≤ 3000]，#cf_span[0 ≤ m ≤ 3000]，#cf_span[1 ≤ q ≤ 4·105]）——分别表示城市数量、道路数量和观光行程数量。接下来的 #cf_span[m] 行每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi, yi ≤ n]，#cf_span[xi ≠ yi]），表示第 #cf_span[i] 条道路从城市 #cf_span[xi] 指向城市 #cf_span[yi]。所有道路均为单向，任意两座城市之间在每个方向上至多有一条道路。接下来的 #cf_span[q] 行每行包含三个整数 #cf_span[sj], #cf_span[tj] 和 #cf_span[kj]（#cf_span[1 ≤ sj, tj ≤ n]，#cf_span[sj ≠ tj]，#cf_span[1 ≤ kj ≤ 3000]）。
## Output
在第 #cf_span[j] 行，输出从 #cf_span[sj] 到 #cf_span[tj] 的理想路径中的第 #cf_span[kj] 座城市。如果从 #cf_span[sj] 到 #cf_span[tj] 不存在理想路径，或者 #cf_span[kj] 大于该路径的长度，请在第 #cf_span[j] 行输出字符串 '_-1_'（不含引号）。
[samples]
**Definitions**
Let $ n, m, q \in \mathbb{Z}^+ $ denote the number of cities, directed roads, and queries, respectively.
Let $ G = (V, E) $ be a directed graph with $ V = \{1, 2, \dots, n\} $ and $ E \subseteq V \times V $, $ |E| = m $, with no self-loops and at most one edge between any ordered pair of distinct vertices.
For any pair of vertices $ s, t \in V $, a **path** from $ s $ to $ t $ is a sequence $ p = (p_1, p_2, \dots, p_k) $ such that:
- $ p_1 = s $, $ p_k = t $,
- $ (p_i, p_{i+1}) \in E $ for all $ i \in \{1, \dots, k-1\} $,
- $ p_i \ne t $ for all $ i < k $ (i.e., $ t $ appears only as the final vertex).
A path $ p $ from $ s $ to $ t $ is **ideal** if it is lexicographically minimal among all paths from $ s $ to $ t $:
For any other path $ q $ from $ s $ to $ t $, let $ i $ be the smallest index such that $ p_i \ne q_i $; then $ p_i < q_i $.
For a query $ (s_j, t_j, k_j) $, let $ P_j $ denote the ideal path from $ s_j $ to $ t_j $, if it exists.
**Constraints**
1. $ 2 \le n \le 3000 $
2. $ 0 \le m \le 3000 $
3. $ 1 \le q \le 4 \cdot 10^5 $
4. For each edge $ (x_i, y_i) $: $ 1 \le x_i, y_i \le n $, $ x_i \ne y_i $, and no duplicate edges.
5. For each query $ (s_j, t_j, k_j) $: $ s_j \ne t_j $, $ 1 \le k_j \le 3000 $.
**Objective**
For each query $ j \in \{1, \dots, q\} $:
- If no ideal path exists from $ s_j $ to $ t_j $, or $ k_j > \text{length}(P_j) $, output $ -1 $.
- Otherwise, output the $ k_j $-th vertex in the ideal path $ P_j $, i.e., $ P_j[k_j] $.
API Response (JSON)
{
"problem": {
"name": "F. Cities Excursions",
"description": {
"content": "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 itse",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF864F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 itse...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Berland 有 #cf_span[n] 座城市。某些城市对之间由 #cf_span[m] 条有向道路连接。人们只能通过这些道路从一座城市移动到另一座城市。不存在连接城市到自身的道路。对于每对城市 #cf_span[(x, y)]，从 #cf_span[x] 到 #cf_span[y] 的道路至多有一条。\n\n从城市 #cf_span[s] 到城市 #cf_span[t] 的路径是一系列城市 #c...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m, q \\in \\mathbb{Z}^+ $ denote the number of cities, directed roads, and queries, respectively. \nLet $ G = (V, E) $ be a directed graph with $ V = \\{1, 2, \\dots, n\\} $ and ...",
"is_translate": false,
"language": "Formal"
}
]
}