Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

Slovak University of Technology

Masaryk University

acm

cz

acm

cz

CTU Open Contest 2007

Catch the Bus!

bus.c, bus.C, bus.p, bus.java

ACM needs to deliver marketing materials to one of their clients. Both ACM and the client em-

ploy students to make such deliveries. And these students use public buses to move throughout

the city. Sometimes, it is necessary to pass the materials as fast as possible.

You are given bus timetables and your task is to find the fastest way for two students to meet

at some stop. The place of the meeting is not important, they only need to meet as early as

possible.

Students may change between any two bus routes at stops that are common for both routes. At

least two minutes are needed for every such change. No additional time is necessary to get on

the first bus or to meet the other student in the target stop.

Input Specification

The input contains a sequence of several scenarios, the sequence is terminated by a line containing

negative number.

Each scenario begins with a non-negative integer L, the number of bus routes that operate in

the city (L . 1000). Every route is then described by two lines. The first line contains names

of stops that the bus runs through. Between each consecutive stops, there is a non-negative

integer specifying the number of minutes required to travel between these stops with the given

bus. The last stop is followed by a negative number.

The second line of each bus route contains non-negative integers separated with spaces. The

first integer H gives the number of buses that depart the initial stop in every hour (H . 60).

The remaining H integers are always distinct and sorted ascendingly, they list the minutes of

departure (between 0 and 59). The timetable repeats every hour. For example, if the second

line says "20030", the buses leave the initial stop at 12:00, 12:30, 13:00, 13:30, 14:00, etc.

After the description of routes, there are two lines that specify the initial position of students.

Each of them will contain time in a standard 24-hour format (one or two digits for hours, colon,

and two digits for minutes) and a stop name.

All numbers, times, and stop names will be separated with a single space. Stop names are

case-sensitive and may be composed only from lower-case and upper-case letters, their length

will not exceed 30 characters. The total number of stops will be at most 1000, the number of

stops on a single route will not exceed 100. The time between any two consecutive stops will be

at most one hour. The routes are considered one-way, if they operate in both directions, they

will be given as two separate routes. A route may run through the same stop several times.

Output Specification

For each test scenario, output a single line containing the earliest possible time the students can

meet at any of the stops. The time must appear in the standard 24-hour format, hours given

as a number between 0 and 23, then colon and minutes between 0 and 59. For hour values less

than 10, only one digit must be used. Be aware of the fact that both students start their trip

on the same day but may meet on another day, if the required time exceeds midnight.

If the students are not able to meet in some scenario, output the words "No connection"instead

of the time.

Sample Input

4

Hradcanska 2 Malostranska 2 Staromestska 2 Mustek 1 Muzeum -1

10 00 06 12 18 24 30 36 42 48 54

Muzeum 1 Mustek 2 Staromestska 2 Malostranska 2 Hradcanska -1

10 03 09 15 21 27 33 39 45 51 57

Andel 2 Karlovo 1 Narodni 2 Mustek 2 Florenc -1

6001020304050

Florenc 2 Mustek 2 Narodni 3 Karlovo 1 Andel -1

6021222324252

12:00 Hradcanska

12:11 Andel

1

Hradcanska 2 Malostranska 2 Staromestska 2 Mustek 1 Muzeum 2 Hradcanska -1

10 00 06 12 18 24 30 36 42 48 54

12:00 Mustek

12:00 Andel

-1

Output for Sample Input

12:20

No connection