Subway

Johny is going to visit his friend Michelle, and his dad lets him make the trip alone by subway. Johny loves riding the subway and would gladly spend half a day underground, but his dad set one condition: change lines as few times as possible.

The city has a lot of stations and several subway lines running through them. All trains are perfectly synchronized. Riding between two consecutive stations of one line takes exactly one minute, and changing lines at a station takes no time at all.

Given the subway map, plan the trip that keeps Johny underground for as long as possible while still obeying his dad.

The first line contains the number of test cases T. The test cases follow.

Each test case starts with an empty line. The next two lines begin with the strings Stops: and Lines:, and list the names of all subway stops and of all subway lines, separated by a comma and a space. After that comes one line per subway line, in no particular order. Such a line begins with <line-name> route: and lists the stops along that line in order. The final two lines give the station near Johny's home and the station near Michelle's home. The two stations are different.

In each test case there are at most 300,000 stations and 100,000 lines, whose total length does not exceed 1,000,000. The names of lines and stations are 1 to 50 characters long and can contain letters, digits, hyphens (-), apostrophes (') and ampersands (&). All lines are bidirectional, although changing the direction of travel counts as a line change, and no line crosses itself, so a line never visits the same station twice.

Print the answers to the test cases in the order in which they appear in the input. For each test case print a single line of the form optimal travel from <start> to <finish>: <L> lines, <M> minutes.

<start> and <finish> are the two station names copied from the input, <L> is the number of lines Johny rides and <M> is the total travel time in minutes. <L> is the smallest number of lines that gets him there, and <M> is the longest travel time among the routes that ride exactly <L> lines. Every boarding adds one to <L>, so riding one line, changing to a second and coming back to the first counts as three lines. Write line instead of lines when <L> is 1, and minute instead of minutes when <M> is 1. You may assume that such a route always exists.