Shortest Path in Directed Labyrinth

You are given a labyrinthine cave with n rooms and m directed passages. Each passage connects one room to another. Your task is to determine the shortest path from room 1 to room \(n\) using these passages.

The cave is represented as a directed graph where each passage is a directed edge from room \(a\) to room \(b\). If a valid path from room 1 to room \(n\) exists, output the sequence of room numbers representing the shortest route; if no such path is available, output -1.

This problem can be efficiently solved with a Breadth-First Search (BFS) algorithm since BFS finds the shortest path in an unweighted graph. The problem input provides the number of rooms, the number of passages, and each passage detailed on a separate line.

inputFormat

The first line of input contains two integers n and m separated by a space, where n denotes the number of rooms and m denotes the number of directed passages.

Each of the next m lines contains two integers a and b representing a directed passage from room a to room b.

outputFormat

If a valid path from room 1 to room \(n\) exists, output the room numbers in the shortest path separated by spaces.

If no such path exists, output -1.

5 5
1 2
2 3
3 5
1 4
4 5

1 4 5