407044: GYM102697 015 Subway System

You're going to a large city with a complex subway system. You need to find out how many subway lines you will take from the airport to your hotel. Given a list of stations that each subway line stops at, print the minimum number of lines you need to take to get from the airport to your hotel.

The first lines contains one integer n, representing the number of different lines in the subway. The next n lines contain an arbitrary number of space-separated strings, each representing the various stations that the subway lines stop at. The airport's station will be Airport in the station list, and the hotel's station will be Hotel. There will not be more than 1000 distinct station names.

Output one positive integer l: the minimal number of different subway lines that you should take to reach the hotel station from the airport station.

4
Airport CityCenter WestStation
CityCenter Library EastStation
WestStation Countryside
Countryside Library Hotel

3

5
Airport TownHall
TownHall Courthouse
Courthouse WestStation
WestStation NorthStation
TownHall Hotel

2

A note from the creator of the problem (Xavier): This problem is really hard. I created the problem and it took me over an hour to come up with a valid solution. Please only attempt this problem if you know what you're doing.