Shortest Friendship Connection Path

You are given a social network where each user is represented by an integer ID. Friendship connections are bidirectional. Given two user IDs, start and end, your task is to determine the shortest chain of friendships that connects them.

The network is described by a list of friendship pairs. If there is a path between the two users, output the sequence of user IDs (separated by spaces) representing the shortest path. If no such path exists, output -1.

You can solve this problem using a breadth-first search (BFS) algorithm. The complexity of BFS is \(O(V+E)\), where \(V\) is the number of users and \(E\) is the number of friendship connections.

inputFormat

The input is read from standard input (stdin) and follows this format:

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

Where:

• start and end are two integers representing the starting and target user IDs.
• m is the number of friendship pairs.
• Each of the next m lines contains two integers u and v, indicating that user u and user v are friends. Note that each friendship is bidirectional.

outputFormat

Output the shortest friendship connection path as a sequence of user IDs separated by a space on a single line. If no path exists between start and end, output -1.

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

1 3 6