(a) Explain how a DFS traversal of the graph modeling the problem and computing the DFS traversal tree rooted at the starting tree can be used to solve this problem. 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 dont have enough information to complete your journey. \includegraphics[width=0.9\textwidth ]{subwayMap.png} Input

The first line of input has an integer, 2N32, 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 N1). 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 az and AZ. 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.

Sample Input 1 Sample Output 1 3 Uptown Midtown Midtown Uptown Downtown Downtown Midtown Uptown Downtown Uptown Midtown Downtown

Sample

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

Sample Input 3

Sample Output 3

4 FirstStop SecondStop SecondStop FirstStop ThirdStop FifthStop FourthStop SixthStop SixthStop FifthStop FirstStop FifthStop no route found