Taking into account the present interest in the Internet, a smart information routing becomes a must. This job is done by routers situated in the nodes of the network. Each router has its own list of routers which are visible for him (so called “routing table”). It is obvious that the information should be directed in the way which minimizes number of routers it has to pass (so called “hop count”). Your task is to find an optimal route (minimal hop count) for the given network form the source of the information to its destination. Input First line contains number of routers in the network (n). Next n lines contain description of the network. Each line contains router ID, followed by a hyphen and comma separated list of IDs of visible routers. The list is sorted in ascending order. Next line contains a number of routes (m) you should determine. The consecutive m lines contain starting and ending routers for the route separated by a single space. Input data may contain descriptions of many networks. Output For each network you should output a line with 5 hyphens and then, for each route, a list of routers passed by information sent from starting to destination routers. In case passing of information is impossible (no connection exists) you should output a string ‘connection impossible’. In case of multiple routes with the same ‘hop count’ the one with lower IDs should be outputted (in case of route form router 1 to 2 as ‘1 3 2’ and ‘1 4 2’ the ‘1 3 2’ should be outputted). Assumptions: A number of routers is not greater than 300 and there are at least 2 routers in the network. Each routers “sees” no more than 50 routers. Sample Input 6 1-2,3,4 2-1,3 3-1,2,5,6 4-1,5 5-3,4,6 6-3,5 6 16 15 24 25 36 21 10 1-2 2-
9 7 3 4 8 10 connection impossible 962