{"raw_statement":[{"iden":"statement","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 itself. For each pair of cities (_x_, _y_) there is at most one road from _x_ to _y_.\n\nA 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.\n\nA 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_.\n\nThere 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_.\n\nFor 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:\n\n*   there is no path from _s__j_ to _t__j_;\n*   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_.\n\nThe 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_).\n\nFor 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."},{"iden":"input","content":"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.\n\nEach 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.\n\nEach 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)."},{"iden":"output","content":"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."},{"iden":"example","content":"Input\n\n7 7 5\n1 2\n2 3\n1 3\n3 4\n4 5\n5 3\n4 6\n1 4 2\n2 6 1\n1 7 3\n1 3 2\n1 3 5\n\nOutput\n\n2\n-1\n-1\n2\n-1"}],"translated_statement":[{"iden":"statement","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] 的路径是一系列城市 #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] 超过一次。\n\n从 #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] 的最小整数。\n\n该国有一家旅游公司提供 #cf_span[q] 项不寻常的观光行程：第 #cf_span[j] 项行程从城市 #cf_span[sj] 开始，到城市 #cf_span[tj] 结束。\n\n对于每对 #cf_span[sj], #cf_span[tj]，请帮助该公司研究从 #cf_span[sj] 到 #cf_span[tj] 的理想路径。注意，从 #cf_span[sj] 到 #cf_span[tj] 可能不存在理想路径，原因有两个：\n\n该公司希望知道从 #cf_span[sj] 到 #cf_span[tj] 的理想路径中第 #cf_span[kj] 座城市（从 #cf_span[sj] 到 #cf_span[tj] 的路径上）。\n\n对于每个三元组 #cf_span[sj], #cf_span[tj], #cf_span[kj]（#cf_span[1 ≤ j ≤ q]），请判断是否存在从 #cf_span[sj] 到 #cf_span[tj] 的理想路径，若存在，请输出该路径中的第 #cf_span[kj] 座城市。\n\n第一行包含三个整数 #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]）——分别表示城市数量、道路数量和观光行程数量。\n\n接下来的 #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]。所有道路均为单向，任意两座城市之间在每个方向上至多有一条道路。\n\n接下来的 #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]）。\n\n在第 #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_'（不含引号）。"},{"iden":"input","content":"第一行包含三个整数 #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]）。"},{"iden":"output","content":"在第 #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_'（不含引号）。"}],"sample_group":[],"show_order":[],"formal_statement":"**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 $ E \\subseteq V \\times V $, $ |E| = m $, with no self-loops and at most one edge between any ordered pair of distinct vertices.  \n\nFor 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:  \n- $ p_1 = s $, $ p_k = t $,  \n- $ (p_i, p_{i+1}) \\in E $ for all $ i \\in \\{1, \\dots, k-1\\} $,  \n- $ p_i \\ne t $ for all $ i < k $ (i.e., $ t $ appears only as the final vertex).  \n\nA path $ p $ from $ s $ to $ t $ is **ideal** if it is lexicographically minimal among all paths from $ s $ to $ t $:  \nFor 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 $.  \n\nFor a query $ (s_j, t_j, k_j) $, let $ P_j $ denote the ideal path from $ s_j $ to $ t_j $, if it exists.  \n\n**Constraints**  \n1. $ 2 \\le n \\le 3000 $  \n2. $ 0 \\le m \\le 3000 $  \n3. $ 1 \\le q \\le 4 \\cdot 10^5 $  \n4. For each edge $ (x_i, y_i) $: $ 1 \\le x_i, y_i \\le n $, $ x_i \\ne y_i $, and no duplicate edges.  \n5. For each query $ (s_j, t_j, k_j) $: $ s_j \\ne t_j $, $ 1 \\le k_j \\le 3000 $.  \n\n**Objective**  \nFor each query $ j \\in \\{1, \\dots, q\\} $:  \n- If no ideal path exists from $ s_j $ to $ t_j $, or $ k_j > \\text{length}(P_j) $, output $ -1 $.  \n- Otherwise, output the $ k_j $-th vertex in the ideal path $ P_j $, i.e., $ P_j[k_j] $.","simple_statement":null,"has_page_source":false}