#include<cstdio>

#include<cstring>

#include<algorithm>

typedef unsigned long long ll;

const int N=300010,M=100010,E=1000010,inf=1000000000;

int Case,n,m,i,j,k,l,D,S,T,a[E],cnt,st[M],en[M],g[N],v[E],nxt[E],ed;

int q[N],h,t,d[N],f[N];bool vis[N],use[M];

char s[18000000],sS[55],sT[55];ll b[N];

inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}

inline bool check(char x){

  if(x>='a'&&x<='z')return 1;

  if(x>='A'&&x<='Z')return 1;

  if(x>='0'&&x<='9')return 1;

  return x=='-'||x=='\''||x=='&';

}

inline ll gethash(int l,int r){

  ll t=0;

  for(int i=l;i<r;i++)t=t*233+s[i];

  return t;

}

inline ll getname(char*s){

  scanf("%s",s);

  int l=strlen(s);ll t=0;

  for(int i=0;i<l;i++)t=t*233+s[i];

  return t;

}

inline int ask(ll x){

  int l=1,r=n,mid;

  while(1){

    if(b[mid=(l+r)>>1]==x)return mid;

    if(b[mid]<x)l=mid+1;else r=mid-1;

  }

}

inline void up(int&x,int y){if(x<y)x=y;}

inline void solve(int x){

  if(use[x])return;

  use[x]=1;

  int i,tmp;

  for(i=st[x];i<=en[x];i++)if(!vis[a[i]])vis[q[++t]=a[i]]=1,d[a[i]]=D+1;

  for(tmp=-inf,i=st[x];i<=en[x];i++)if(d[a[i]]==D)up(tmp,f[a[i]]-i);else up(f[a[i]],tmp+i);

  for(tmp=-inf,i=en[x];i>=st[x];i--)if(d[a[i]]==D)up(tmp,f[a[i]]+i);else up(f[a[i]],tmp-i);

}

int main(){

  scanf("%d",&Case);

  while(Case--){

    scanf("%s",s);

    gets(s);

    l=strlen(s);

    for(n=i=0;i<l;)if(!check(s[i]))i++;else{

      for(j=i;j<l&&check(s[j]);j++);

      b[++n]=gethash(i,j);

      i=j;

    }

    std::sort(b+1,b+n+1);

    for(ed=0,i=1;i<=n;i++)g[i]=0;

    scanf("%s",s);

    gets(s);

    l=strlen(s);

    for(m=i=0;i<l;)if(!check(s[i]))i++;else{

      for(j=i;j<l&&check(s[j]);j++);

      m++;

      i=j;

    }

    for(cnt=0,k=1;k<=m;k++){

      scanf("%s",s);

      scanf("%s",s);

      gets(s);

      l=strlen(s);

      st[k]=cnt+1;

      for(i=0;i<l;)if(!check(s[i]))i++;else{

        for(j=i;j<l&&check(s[j]);j++);

        a[++cnt]=ask(gethash(i,j));

        i=j;

      }

      en[k]=cnt;

      for(j=st[k];j<=en[k];j++)add(a[j],k);

      use[k]=0;

    }

    scanf("%s",s);

    scanf("%s",s);

    scanf("%s",s);

    S=ask(getname(sS));

    scanf("%s",s);

    scanf("%s",s);

    scanf("%s",s);

    T=ask(getname(sT));

    for(i=1;i<=n;i++)d[i]=inf,f[i]=vis[i]=0;

    d[S]=f[S]=0;

    vis[S]=1;

    q[h=t=1]=S;

    while(h<=t){

      D=d[q[h]];

      while(h<=t&&d[q[h]]==D)for(i=g[q[h++]];i;i=nxt[i])solve(v[i]);

    }

    printf("optimal travel from %s to %s: %d line",sS,sT,d[T]);

    if(d[T]>1)putchar('s');

    printf(", %d minute",f[T]);

    if(f[T]>1)putchar('s');

    puts("");

  }

  return 0;

}