This page is still under construction.

Parts of this page are still being built. What you see may change.

Catch the Bus!

Time limit1sMemory limit128 MB

Summary
Given bus routes with hourly timetables and two students' start times and stops, find the earliest moment they can meet at any shared stop, considering 2-minute transfer times.
Level

Hard8 of 10

Topics
Shortest path, Graph, Simulation, Implementation
Solved
No attempts yet

Problem

ACM needs to deliver marketing materials to one of their clients. Both ACM and the client employ students to make the deliveries, and these students travel around the city by public bus. Sometimes the materials must be handed over as fast as possible.

You are given the city's bus timetables. Find the earliest moment at which two students can meet at some stop. The meeting place does not matter — they only need to meet as early as possible.

A student may transfer between two bus routes at any stop the routes have in common. Every transfer takes at least 2 minutes. Boarding the very first bus takes no extra time, and meeting the other student at the target stop takes no extra time either.

Input

The input contains several scenarios, one after another. The sequence ends with a line containing a negative number.

Each scenario begins with a non-negative integer LL, the number of bus routes operating in the city (L≤1000L \le 1000). Each route is then described by two lines.

  • The first line lists the stops the bus runs through. Between every two consecutive stops there is a non-negative integer, the number of minutes needed to travel between them on that bus. A negative number follows the last stop.
  • The second line starts with a non-negative integer HH, the number of buses that leave the initial stop each hour (H≤60H \le 60). The remaining HH integers are distinct and sorted in increasing order; they are the departure minutes (from 00 to 5959). The timetable repeats every hour. For example, 2 00 30 means buses leave the initial stop at 12:00, 12:30, 13:00, 13:30, 14:00, and so on.

After the routes come two lines giving the students' starting positions. Each line contains a time in the standard 24-hour format (one or two digits for the hour, a colon, and two digits for the minute) followed by a stop name.

All numbers, times, and stop names are separated by a single space. Stop names are case-sensitive, consist only of lower-case and upper-case letters, and are at most 3030 characters long. The total number of stops is at most 10001000, and a single route visits at most 100100 stops. The travel time between any two consecutive stops is at most one hour. Routes are one-way; a route that runs in both directions is given as two separate routes. A route may pass through the same stop several times.

Output

For each scenario, print a single line with the earliest time the two students can meet at any stop. Use the standard 24-hour format: the hour is a number from 00 to 2323, followed by a colon and the two-digit minute (from 0000 to 5959). Print hour values below 1010 with a single digit. Both students start on the same day, but they may meet on a later day if the required time passes midnight.

If the students cannot meet in a scenario, print No connection instead.

Examples1

  1. Example 1

    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
    6 00 10 20 30 40 50
    Florenc 2 Mustek 2 Narodni 3 Karlovo 1 Andel -1
    6 02 12 22 32 42 52
    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
    
    Expected output
    12:20
    No connection