P7010 [CERC2013] Subway
题目描述
$Johny$ 准备去拜访他的朋友 $Michelle$。他的父亲允许他乘地铁独自去那里。$Johny$ 喜欢乘地铁旅行，并很愿意用这次机会在地铁里呆上半天，但是父亲要求他尽量减少换乘次数。这个城市有很多地铁车站，并有几条地铁线路连接它们。所有列车都完全同步——在每条线上的两个连续地铁站点之间地铁行驶的时间恰好需要 $1$ 分钟，而在该城市的任何一个地铁站点上更改线路是不需要花费时间的。
现在 $Johny$ 有了该城市的地铁线路图，请帮助 $Johny$ 计划行程，以便他可以尽可能长时间的在地铁里呆着，同时还要尽量减少换乘次数。
输入格式
输入的第 $1$ 行为测试数据 $T$ 的数量。
每组测试数据均用空行分隔。接下来的两行以字符串以 $ Stops: $ 和 $Lines: $ 开头，并分别包含所有地铁站和线路的名称（以逗号和空格分隔）。每条地铁线路中的其中一条线路（不分先后）从 $route: $ 开始，并一一列出了该条线路的站点名称。最后两行给定了 $Johny$ 和 $Michelle$ 的家附近的车站的名称。
在每组测试数据中，最多有 $300000$ 个站点以及 $100000$ 条铁路线路，保证其总长度不超过 $1000000$；铁路线路和地铁站点的名称长度均在 $1$ 至 $50$ 个字符之间，其名称中可以含有字母、数字、连字符 `-`、引号 `'` 和特殊符号 `&`。所有的地铁线路都是双向的（改变行进方向即该条线路被改变），并保证没有自交叉。
输出格式
按照在输入中测试数据的顺序来输出每组测试数据的答案。对于每组测试用例，需输出一行来总结 Johny 可以采用的最佳路线（参见样例输出）。假设这样的线路始终存在。
### 输入输出样例
**输入 #1**
```txt
3
Stops: OxfordCircus, PiccadillyCircus, HydeParkCorner, King'sCross, GreenPark, Arsenal, Victoria, Highbury&Islington, LeicesterSquare
Lines: Blue, Cyan
Cyan route: Highbury&Islington, King'sCross, OxfordCircus, GreenPark, Victoria
Blue route: HydeParkCorner, GreenPark, PiccadillyCircus, LeicesterSquare, King'sCross, Arsenal
Johny lives at King'sCross
Michelle lives at GreenPark
Stops: OxfordCircus, PiccadillyCircus, HydeParkCorner, King'sCross, GreenPark, Arsenal, Victoria, Highbury&Islington, LeicesterSquare
Lines: Blue, Cyan
Cyan route: Highbury&Islington, King'sCross, OxfordCircus, GreenPark, Victoria
Blue route: HydeParkCorner, GreenPark, PiccadillyCircus, LeicesterSquare, King'sCross, Arsenal
Johny lives at PiccadillyCircus
Michelle lives at LeicesterSquare
Stops: OxfordCircus, PiccadillyCircus, HydeParkCorner, King'sCross, GreenPark, Arsenal, Victoria, Highbury&Islington, LeicesterSquare
Lines: Blue, Cyan
Cyan route: Highbury&Islington, King'sCross, OxfordCircus, GreenPark, Victoria
Blue route: HydeParkCorner, GreenPark, PiccadillyCircus, LeicesterSquare, King'sCross, Arsenal
Johny lives at Victoria
Michelle lives at HydeParkCorner
```
**输出 #1**
```txt
optimal travel from King'sCross to GreenPark: 1 line, 3 minutes
optimal travel from PiccadillyCircus to LeicesterSquare: 1 line, 1 minute
optimal travel from Victoria to HydeParkCorner: 2 lines, 7 minutes
```
说明/提示
时间限制：$8s$
内存限制：$256\texttt{MB}$