You are building an app for a newly created bus system connecting Harrisonburg to Charlottesville. There are many different bus routes each of which travels between named stops along its route. Not all of the bus routes cross each other, so it is possible that there are some pairs of stops where there is no way of getting on a bus at the first stop and making changes to get to the final stop. Your task is to implement a graph search function that can determine a sequence of stops a user can use to get from a starting stop to an ending stop, or to tell the user that there is no bus route possible between those two stops.

Input

The bus route segments are described as single stretches of road between two consecutive stops. All such pairs will be described in one direction, but all bus routes are bidirectional, since buses travel in both directions along each route.

The first line of input has an integer n that is the number of road segments between consecutive stops. The next n lines of input describe the consecutive stops, each of which is named by a string of alphabetical characters with no spaces. The line will contain both of the stops of the segment, separated by a space.

The final line of input is the query, which is two stop names separated by a space.

Output

Give a sequence of stop names starting at the starting stop of the query and ending at the ending stop separated by spaces (if one exists), or output "no route possible" if none is found.

Sample Input	Sample Output
2 Hburg JMU Charlottesville JMU Hburg Charlottesville	Hburg JMU Charlottesville
4 Hburg JMU JMU Upark Upark Hburg CVO UVA Hburg UVA	no route possible

Larger example files (the one used on Gradescope) can be downloaded here: bus_stops_t3_in.txt Download bus_stops_t3_in.txt bus_stops_t3_exp.txt Download bus_stops_t3_exp.txt Depending how you implement your graph, the order of stops on the path may not be unique, so, checking your solution requires writing a bit more code to validate your path (and of course, that is optional).

Hints:

Store the stops in a dictionary and use a set for the edge list.
You will need to implement a method that uses a spanning tree. The lab is asking you for a path between the locations (not necessarily the shortest path).

Submission:

Your code in a file name cs412_bus_stops_a.py and submit your code to gradescope.

Rubrics:

(6 points) program solves the examples
(3 points) solves the hidden examples
(1 point) instructor review