You have arrived in The Big City but your journey is not yet complete. You must still navigate the subway and get to your final destination. The information booth in the subway station is unattended and fresh out of maps of the subway system. On the floor you notice fragments of a map. Can you piece together enough of the map to figure out how to get to your final destination?

Each fragment of the map happens to perfectly contain a single subway station while also identifying all of the other stations that it connects to. Each connection between stations is bi-directional such that it can be travelled going either direction. Using all of the available fragments, your task is to determine the sequence of stations you must pass through in order to reach your final destination or state that there is no route if you don’t have enough information to complete your journey.

-----Input-----
The first line of input has an integer, $2 \leq N \leq 32$, that identifies the number of pieces of the map that were found.

The following $N$ lines each describe a station depicted on one of those pieces. Each of these lines starts with the name of the station they describe and is followed by a space-separated list of all of the station names that are directly connected to that station (there may be as many as $N-1$).

The final line identifies a starting station and a destination station. The destination station is guaranteed to be different than the starting station.

Each station name is a string of up to $20$ characters using only letters a–z and A–Z. It is guaranteed that there is at most one simple route (without revisiting stations) from the starting station to the destination station.

-----Output-----
Give the sequence of stations that leads from the starting station to the destination station. Separate station names with spaces. If there are not enough pieces of the map to find a route from the starting station to the destination station then output “no route found”.

-----Examples-----
Sample Input 1:
3
Uptown Midtown
Midtown Uptown Downtown
Downtown Midtown
Uptown Downtown
Sample Output 1:
Uptown Midtown Downtown

Sample Input 2:
6
A B
B A D
C D
E D F G
F E
G E
F A
Sample Output 2:
F E D B A

Source: kattis | Difficulty: MEDIUM
Tags: Graph algorithms


Solutions: