시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 66 20 18 33.962%

문제

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.

입력

The first line of input has an integer, 2 ≤ N ≤ 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

출력

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”.

예제 입력

3
Uptown Midtown
Midtown Uptown Downtown
Downtown Midtown
Uptown Downtown

예제 출력

Uptown Midtown Downtown

예제 입력 2

6
A B
B A D
C D
E D F G
F E
G E
F A

예제 출력 2

F E D B A

예제 입력 3

4
FirstStop SecondStop
SecondStop FirstStop ThirdStop
FifthStop FourthStop SixthStop
SixthStop FifthStop
FirstStop FifthStop

예제 출력 3

no route found

힌트