Задача . F. Экскурсии по городам

В Берляндии есть n городов. Некоторые пары городов соединены m односторонними дорогами. Из одного города в другой можно добраться только по этим дорогам. При этом нет дорог, соединяющих город с самим собой. Для любой пары городов (x, y) может быть не более одной дороги из x в y.

Путь из города s в город t представляет собой последовательность городов p₁, p₂, ... , p_k, где p₁ = s, p_k = t, где из города p_i идет дорога в город p_i + 1 для все i от 1 до k - 1. Через любой из городов, кроме последнего города t пути, путь может проходить многократно. Через город t многократно путь проходить не может.

Путь p из s в t называется идеальным, если он является лексикографически минимальным таким путем. Иными словами, p — идеальный путь из s в t, если для любого другого пути q из s в t p_i < q_i, где i — наименьший индекс такой, что p_i ≠ q_i.

В стране работает туристическое агенство, которое предоставляет q необычных экскурсий: j-я экскурсия начинается в городе s_j и заканчивается в городе t_j.

Помогите туристическому агентству для каждой пары s_j, t_j проанализировать идеальный путь из s_j в t_j. Заметим, что идеальный путь из s_j в t_j может не существовать. Такое возможно по двум причинам:

• из города s_j невозможно добраться по дорогам в город t_j;
• из города s_j возможно добраться по дорогам в город t_j, но для любого такого пути p найдется другой путь q из s_j в t_j, что p_i > q_i, где i — первый индекс, что p_i ≠ q_i.

Анализ идеального пути из s_j в t_j состоит в нахождении города, который является k_j-м в этом пути (при следовании из s_j в t_j).

Напишите программу, которая для каждой тройки s_j, t_j, k_j (1 ≤ j ≤ q) определит, существует ли идеальный путь из s_j в t_j и выведет k_j-й город пути, если таковой есть.