Johny 准备去拜访他的朋友 Michelle。他父亲允许他独自乘坐地铁前往。Johny 热爱乘坐地铁，并乐于借此机会在地下待上半天，但他父亲要求他尽可能减少换乘线路的次数。城市里有许多车站，以及多条连接它们的地铁线路。所有列车都完全同步——在每条线路上，相邻两站之间的行程恰好需要一分钟，而在任何车站换乘线路都不需要时间。

给定地铁线路图，请帮助 Johny 规划他的行程，使他在满足父亲要求的前提下，尽可能长时间地乘坐地铁。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述：

每个测试用例的描述以一个空行开始。接下来的两行分别以字符串 Stops: 和 Lines: 开头，分别包含所有地铁站和线路的名称（以逗号和空格分隔）。随后是每条地铁线路的描述（顺序不限），以 <line-name> route: 开头，并列出该线路沿途的站点名称。最后两行分别指定了 Johny 家和 Michelle 家附近的（不同）车站名称。

在每个测试用例中，最多有 $300\,000$ 个车站和 $100\,000$ 条线路，线路总长度不超过 $1\,000\,000$。线路和车站名称的长度在 1 到 50 个字符之间，可以包含字母、数字、连字符 (-)、撇号 (‘) 和“与”符号 (&)。所有线路都是双向的（尽管改变行驶方向算作一次换乘），且线路之间没有自交。

输出格式

按输入中出现的顺序打印每个测试用例的答案。对于每个测试用例，打印一行总结 Johny 可以采取的最优路线（具体格式见样例输出）。你可以假设这样的路线总是存在的。

样例

输入 1

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

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