Shortest Path in an Undirected Graph Using BFS

You are given an undirected graph with n nodes and m edges. The graph is provided as a list of edges. Your task is to find the shortest path from a given starting node to a destination node using the Breadth-First Search (BFS) algorithm.

If there exists a path from the start to the destination, output the sequence of nodes along this shortest path separated by single spaces. If no such path exists, output -1. In the case that the starting node is the same as the destination, simply output that node.

Note: When there are multiple shortest paths, you must output the one discovered first by performing BFS while exploring the adjacent nodes in increasing order.

Recall that the time complexity of the BFS algorithm is \(O(n + m)\), where \(n\) is the number of nodes and \(m\) is the number of edges.

inputFormat

The input is given from standard input (stdin) in the following format:

n
m
u1 v1
u2 v2
...
um vm
start end

Where:

• n is the number of nodes.
• m is the number of edges.
• Each of the next m lines contains two integers u and v indicating that there is an undirected edge between nodes u and v.
• The last line contains two integers: start and end, representing the starting and destination nodes respectively.

outputFormat

Output to standard output (stdout) the shortest path from the start node to the destination node as a sequence of node numbers separated by a single space. If no path exists, output -1.

## sample

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

1 3 5 6