Bus Schedules

The Association of Commuters in Montreal (ACM) wishes to create a website for the city’s publictransit commuters, in order to promote public transit. A prominent reason for people to drive to work instead of commuting is the time wasted on the subway and buses. For this reason, the ACM wishes to add a form on their website so that visitors will be able to specify two points on the island, and the website will find the quickest route between those two points using its database of subway and bus schedules.

Seeing how this may help improve the environment and the greenhouse effect, you offer your help.

The first line of each test case will contain a positive integer n, the number of bus and subway schedules which will follow. Each schedule will begin with a line containing a positive integer m, the number of stops along the path. m lines will follow, describing the stops of the day in chronological order. Each stop will begin by a time in the format hh : mm, between 00 : 00 and 23 : 59 inclusively. There will be at least one minute between each stop — in other words, all the stop times for a particular bus will be different. A single space will follow, and the rest of the line will contain a name describing the stop.

The name will not contain spaces nor capital letters, and will be at most 20 characters long. Stops with the same name obviously denote the same physical location, where passengers can wait for other buses or subways to stop. After the day completes, the buses and subways mysteriously disappear and reappear at some point before their first stop. They cannot carry any passengers at that time, so the passengers must spend the night waiting at some stop.Each schedule repeats itself every day.

After the schedules, a line will contain a time and two locations of at most 20 characters, the start and the goal. Output the minimum number of minutes needed for a passenger at the start location at the given time to reach the goal location. He is able to enter any bus which stops at his start location at the given starting time or later, and he can also switch from a bus to another instantaneously if they happen to stop at the same place at the same time. He can also wait at a stop for an arbitrary amount of time.

If the destination cannot be reached, output “impossible”.
The last line of the input will contain the integer 0 and should not be processed.
All the numbers in the input will be at most 1000.

2
4
00:01 loc_a
00:02 loc_b
00:10 loc_c
00:20 loc_a
2
00:02 loc_b
00:04 loc_c
00:00 loc_a loc_c
1
3
00:00 foo
01:00 bar
02:00 baz
01:30 bar foo
1
4
00:00 baz
01:00 foo
02:00 bar
03:00 baz
02:30 bar foo
0

4
impossible
2790

IPCP 2005 Northern Preliminary for Northeast North-America