Input file: rom.in
Output file: rom.out

　　有一个古老的俗语："条条道路通罗马"。如果说那是对的，那么对于任意两个城市之间找一条路是很简单的。从A城出发到B城，旅行者可以沿着一条路从A到罗马，然后从罗马到B城。当然存在一条最短的路。

　　罗马帝国的公路网络有一个简单的结构：从罗马开始，有一些道路延伸到附近的城市。从这些城市更多道路延伸到更远的城市，以此类推。因此，城市可被看成以不同的层次围着罗马。对于第I层的城市仅与第I-1层和第I+1层的城市联结（罗马被看成第0层）。在公路网中没有任何的环，一个第I层的城市仅与第I-1层中唯一的城市相通，但在第I+1层中有0个或多个城市与它相连）。所以，从一个给定的第I层的城市到罗马，旅行者只要沿着一条通向I-1层次城市的道路，重复这个操作，每一步使得他离罗马更近一点。

　　给定一个城市公路网，你的任务是在任意给出的城市之间找出一条最短的路线，这里两城的距离是指一条路上两个城市之间的城市数。

　　输入要求：

　　输入的第一行包含两个整数M和N（之间用空格隔开），M表示公路网中道路数。接着M行包含一对城市的名字（中间有一个空格），一个城市的名字包含最多10个字母，并且每个名字的首字母是大写。任意两个城市名字以不同字母开始。罗马的名字在输入中至少出现一次，它被认为0层（最低层），城市名字对表示一条路连着两个城市，第一城市的层次比第二个城市的层次低。路的结构符合以上的规则。输入中没有任意两行是重复的。

　　再接着N行，每行的城市名字对（一个空格隔开，且是前M行中有的城市），这些城市对是"询问对"。你的任务是对于每一"询问对"，找一条最短的路从第一名字的城市到第二个城市。

　　输出要求：

　　对于N个"询问对"的每一对，输出一行大写字母序列（城市名首字母序列），表示"询问对"中两个城市之间最短路线。

　　Sample input

　　7 3
　　Rome Turin
　　Turin Venice
　　Turin Genoa
　　Rome Pisa
　　Pisa Florence
　　Venice Athens
　　Turin Milan
　　Turin Pisa
　　Milan Florence
　　Athens Genoa

　　Sample output

　　TRP
　　MTRPF
　　AVTG