// Slow solution for problem D
// Author: Adam Polak
// Modification of a correct solution. Single line processing time becomes
// quadratic if it can be reached from many stops in the same phase.

#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

inline int Abs(int x) { return x < 0 ? -x : x; }

int main() {
  ios_base::sync_with_stdio(0);
  int Z;
  cin >> Z;
  cin.ignore();  // ignore end-of-line
  while (Z--) {
    vector<vector<string>> lines;
    map<string, vector<int>> stops;
    map<string, int> max_stops_until;
    string start, target;
   
    string buf;
    getline(cin, buf);  // skip empty line
    getline(cin, buf);  // we don't care about stops' names
    getline(cin, buf);  // nor lines' names
    while (true) {
      getline(cin, buf);
      if (buf.substr(0, string("Johny lives").length()) == "Johny lives")
        break;
      istringstream s(buf);
      string token;
      s >> token >> token;  // skip line name and "route:"
      lines.push_back(vector<string>());
      while (s >> token) {
        if (token.back() == ',')
          token.resize(token.size() - 1);
        lines.back().push_back(token);
      }
    }
    start = buf.substr(string("Johny lives at ").length());
    getline(cin, buf);
    target = buf.substr(string("Michelle lives at ").length());

    for (int i = 0; i < lines.size(); ++i)
      for (const string& stop : lines[i])
        stops[stop].push_back(i);

    vector<string> curr_stops;
    curr_stops.push_back(start);
    max_stops_until[start] = 0;
    int num_lines = 0;
    vector<bool> is_line_visited(lines.size());
    while (max_stops_until.count(target) == 0) {
      map<string, int> new_max_stops_until;
      for (const string& stop : curr_stops)
        for (int line_id : stops[stop])
          if (!is_line_visited[line_id]) {
            const vector<string>& line = lines[line_id];
            vector<pair<int, int>> reachable_stops;
            for (int i = 0; i < line.size(); ++i)
              if (max_stops_until.count(line[i]))
                reachable_stops.push_back(
                    make_pair(i, max_stops_until[line[i]]));
            for (int i = 0; i < line.size(); ++i)
              if (!max_stops_until.count(line[i])) {
                int best = -1e9;
                for (pair<int, int> cand : reachable_stops)
                  best = max(best, Abs(i - cand.first) + cand.second);
                new_max_stops_until[line[i]] =
                    max(new_max_stops_until[line[i]], best);
              }
            is_line_visited[line_id] = true;
          }
      curr_stops.clear();
      for (const auto& it : new_max_stops_until) {
        curr_stops.push_back(it.first);
        max_stops_until[it.first] = it.second;
      }
      num_lines++;
    }

    int num_stops = max_stops_until[target];
    cout << "optimal travel from " << start << " to " << target
         << ": " << num_lines << (num_lines > 1 ? " lines" : " line")
         << ", " << num_stops << (num_stops > 1 ? " minutes" : " minute")
         << endl;
    
  }
  return 0;
}