CF864F Cities Excursions

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 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

The first line contains three integers $ n $ , $ m $ and $ q $ ( $ 2

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.