Intergalactic Highways
The world is on constant evolution, the humans evolved to a galactic civilization at the year 700,000, they are now capable of going instantly to any other planet in 1 unit of time, however, they must stop sometimes in a planet to avoid a horrible collision against an asteroid.
Rudolph-X3000, a single humanoid, wants to visit his family visiting as fewer planet as possible from planet A to planet B inclusive without repeating any planet, he is in a hurry so he need the answer quickly. Can you determine how many planets is going to visit?
As Rudolph-X3000 is an intergalactic traveler, he want to determine the planets he is going to visit as well, if there exists more than a single shortest path between planet A and B, print the one lexicographically smallest, if there isn't exists such route, print -1.
The human race knows now the Delta Velocity, this velocity allows to move in a single unit of time at a very fast speed from a place i to place j. So you can consider the distance between planets will be always of 1.
INPUT:
The first line will contain an integer T representing T test cases
Then, in the next line, there will be an integer R denoting the number of relations between planet, a relation is considered so that from a planet i you can go to planet j, this relation is symmetric, so the path between (i,j) is the same as (j,i)
The next R lines will contain two strings P and Q, these strings will denote the name of a planet P and a name of a planet Q and their relation.
The last line will contain two strings S and D, representing the origin planet and the destiny planet.
Note: All the strings will have the combination of uppercase and lowercase letters [A-Z] [a-z].
OUTPUT:
For each test case you shall print the string “Scenario #i: “ where i is the test case you're analyzing (starting from 1) followed by the minimum number of planets, then, in the next line, you should list each planet visit (including origin and destiny), each one separated by a single space.
SAMPLE CASE:
|
INPUT |
OUTPUT |
|
3 8 Mercury Venus Venus Earth Earth Mars Mars Jupiter Jupiter Saturn Saturn Uranus Uranus Neptune Neptune Pluto Earth Pluto 7 Mesopotamia Merrick Merian Earth Earth Venus Merian Merrick Venus Mesopotamia Pluto Earth Mesopotamia Pluto Mesopotamia Earth 2 Earth Sun Moon Venus Earth Moon |
Scenario #1: 7 Earth Mars Jupiter Saturn Uranus Neptune Pluto Scenario #2: 3 Mesopotamia Pluto Earth Scenario #3: -1 |
Explanation of the second case:
There are two possible routes for going from Mesopotamia to Earth, one is “Mesopotamia → Pluto → Earth”, the other one is “Mesopotamia → Venus → Earth”, we select the lexicographically smaller.
CONSTRAINTS:
1<=T<=100
1<=R<=100,000
1<=|{P.Q.S.D}|<=50
It is safe to say that there will be no more than 10,000 distinct planets.