Johny is going to visit his friend Michelle. His dad allowed him to go there on his own by subway. Johny loves traveling by subway and would gladly use this opportunity to spend half a day underground, but his dad obliged him to make as few line changes as possible. There are a lot of stations in the city, and several subway lines connecting them. All trains are perfectly synchronized -- the travel between two consecutive stations on every line takes exactly one minute, and changing lines at any station takes no time at all. Given the subway map, help Johny to plan his trip so that he can travel for as long as possible, while still following his dad’s order. \InputFile First line of input contains the number of test cases \textbf{T}. The descriptions of the test cases follow: The description of each test case starts with an empty line. The next two lines begin with the strings \textbf{Stops}: and \textbf{Lines}:, and contain the names (separated by a comma and a space) of all subway stops and lines, respectively. A single line for each subway line follows (in no particular order), beginning with \textbf{ route:} and listing the names of the stops along this particular line. The final two lines specify the names of the (different) stations nearby Johny’s and Michelle’s homes. In each test case, there are at most \textbf{300000 }stations and \textbf{100000 }lines, whose total length does not exceed \textbf{1000000}. The names of lines and stations are between \textbf{1 }and \textbf{50 }characters long and can contain letters, digits, hyphens (\textbf{-}), apostrophes (\textbf{'}) and "\textbf{and}" signs (\textbf{&}). All lines are bidirectional (although changing the direction of travel counts as a line change) and there are no self-crossings. \OutputFile 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 summarizing the optimal route Johny can take (see example output for exact format). You may assume that such a route always exists. \textbf{Warning}: \textit{Some lines in the example test data below were too long and had to be wrapped. You can access full sample tests at your workstation}.