#4053. [Cerc2013]Subway

题目描述

小J要坐地铁到小M家去玩。有很多的地铁站，有很多条双向的地铁线路连接它们。从一个站到一个直接相邻的站都只要1min，换线不需要时间。给你地铁图，你的任务是帮助小J安排他的路线，使得换乘（在一条线路上回头也算换乘）次数尽量少，且让他坐的尽量久。

输入格式

第一行包含一个数T，代表数据组数

每一组测试数据如下:

每组数据用一个回车开头，接下来的两行以"Stops:"和"Lines:"(不包含引号)开头，并且分别包含站点和线路的名称，之间用一个逗号和一个空格隔开。接下来对于每条线路有单独的一行，以线路的名称+" route:"开头，后面包含它经过的站点，之间用一个逗号和一个空格隔开。最后两行告诉你小J与小M的位置。

输出格式

对于每组测试数据，打印单独的一行代表小J的最优线路（详情请见样例数据），保证最优路径存在。

样例

样例输入

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

样例输出

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

数据范围与提示

站点数<=300000 线路数<=100000 线路总长度<=1000000 名称长度<=50 名称可以包括字母、数字、减号(-)、单引号(')、and标志(&)，保证没有自环。