015. Subway System
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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

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.

Examples
Input
4
Airport CityCenter WestStation
CityCenter Library EastStation
WestStation Countryside
Countryside Library Hotel
Output
3
Input
5
Airport TownHall
TownHall Courthouse
Courthouse WestStation
WestStation NorthStation
TownHall Hotel
Output
2
Note

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.