CF59E Shortest Path

In Ancient Berland there were $ n $ cities and $ m $ two-way roads of equal length. The cities are numbered with integers from $ 1 $ to $ n $ inclusively. According to an ancient superstition, if a traveller visits three cities $ a_{i} $ , $ b_{i} $ , $ c_{i} $ in row, without visiting other cities between them, a great disaster awaits him. Overall there are $ k $ such city triplets. Each triplet is ordered, which means that, for example, you are allowed to visit the cities in the following order: $ a_{i} $ , $ c_{i} $ , $ b_{i} $ . Vasya wants to get from the city $ 1 $ to the city $ n $ and not fulfil the superstition. Find out which minimal number of roads he should take. Also you are required to find one of his possible path routes.

N/A

N/A