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.