IGALAXY - Intergalactic Highways

ORIGINAL STATEMENT.

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 few planets 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 one single shortest path between planet A and B, print the one lexicographically smallest, if there is no 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 destination 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 destination), each one separated by a single space.

Example

Input:
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

Output:
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.


Added by:Venezuelan Programming League
Date:2012-08-08
Time limit:4.528s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2015-01-22 13:58:05 vsri293
stl..stl..stl... :)
2014-01-21 16:10:04 Aditya Bahuguna
:) Finally!!!!
2014-01-02 12:47:16 shiva_hellgeek
Finally AC after many WAs
I was really doing a stupid mistake. :D
2013-06-16 14:02:02 fitcat
I don't know why I got WA (verified with over a thousand random cases with a AC one). After rewriting it using C++ string instead of C string, then AC.
2012-09-11 20:08:08 Aman Gupta
even I' getting WA on the 5th Judge.. any tough test cases?
EDIT: remember lexicographic ordering!

Last edit: 2012-10-24 17:17:38
2012-09-05 08:19:42 ♘Prabhat
no. of distinct planets can more than 10000, i got 4 runtime error due to this....

The generator is ok, i tested it with the constraints given, greetings, VPL

Last edit: 2012-11-01 22:07:01
2012-09-01 12:13:06 Archit Mittal
can somebody give some tough test case as i cant understand why am i getting WA at 5th judge

Last edit: 2012-09-01 12:21:27
2012-08-29 13:54:17 Noszály Csaba
@problemsetter: I am 93.731% sure that strings may have "no letter" chars. :)
Correct me if i am wrong.
Anyway, it is a good classical problem.
2012-08-13 12:33:02 :D
I solved it under following assumptions:

1. Names are case sensitive.
2. Lexicographical order is in terms of ascii values. That is, in C/C++ it would be the strcmp ordering.

There is one "special" thing that I missed first time around, but I think it shouldn't be spoiled. Remember that in the input you have JUST the edges described.
2012-08-13 11:25:34 Islam Diaa
I don't know why I am getting WA. Does anyone have any special cases?
Also @problem setter, can two similar strings which are different in their cases exist in the same input? For example "earth" and "EaRth" ??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.