My home town, Rhyl, has a one-way traffic system which seems to have been designed to keep people away from their destination for as long as possible. Your task, should you choose to attempt it, is to produce a program to give the shortest route through such a traffic system.
Input will be on
STDIN, and will be a list of start and end points followed by a blank line followed by a list of queries, as follows:
A B B A B C C D D C A D C A B A
Each road can only be travelled in the direction(s) given, so, in the above example the road A - B is a two way street whereas B - C is a one-way street from B to C. Travelling from C to B is prohibited.
Start and end points will all be represented by a single upper-case letter.
Output should be the shortest route (measured by number of points visited) from the given start point to the given end point for each query received. If no such route exists, output a blank line. If more than one shortest route exists, output the first when sorting all shortest routes lexicographically.
For the above example the output would be:
A B C D B A
and also tests and expected output for anyone who can't use the above scripts
./test [your program and its arguments]
All answers which have obviously had some attempt at golfing that meet the spec and pass all the tests will get my upvote. The shortest working answer by 26/01/2012 will be accepted.