Problem C
Passing Secrets

In the public school system, passing secret messages between students is a serious enterprise with a proud, noble history. At the Junior Computer Scientist High School, industrious students have discovered the idea of peer-to-peer networking and have adapted this to message passing. If one student has a message to deliver to another, they may be able to pass the message directly from the sender to the receiver if they are in the same group (a group is either a class, an organization, or a club). Of course, if the sender and the receiver don’t have any meetings in common, they may have to pass the message through one or more intermediaries. For example, if Alice needs to pass a message to Bob, Alice may have Calculus class with Sherry. Sherry may have chess club with Erica and Erica may be in band with Bob. Passing the message via Sherry and Erica would permit Alice to reach Bob even if the two of them don’t get a chance to meet directly.

Of course, passing messages involves some risk that the message is read by a third party. We’ll measure the risk in passing a message as a function of the number of intermediaries and the sizes of the group meetings during which the message must be passed. Each intermediary that must help to pass the message from sender to receiver represents one point of risk. Likewise, each meeting in which the message must be passed along represents an additional $k - 2$ in risk, where $k$ is the number of people in the meeting. This component of risk reflects the fact that the more people there are at a meeting, the more risk there is of someone else getting to see the message.

Under this risk assessment scheme, if Alice and Bob are the only participants in Ancient Egyptian Algebra Club, they can pass notes to each other with zero risk. If Alice must pass a note to Bob by giving it to Sherry a Calculus class of size $10$, and Sherry must give the note to Erica in a chess club of size $15$ and Erica must hand the note to Bob in band with $50$ people, the total risk would be $(10 - 2) + (15 - 2) + (50 - 2)$ for the sizes of the meetings plus $2$ more for the two intermediaries, for a total of $71$.

Input

Input consists of up to $20$ risk assessments. Each risk assessment starts with a line giving a pair of names, $a$ and $b$. The next line has an integer $1 \le n \le 100$ giving the number of groups at the school. Each of the next $n$ lines lists all of the participants in one of the groups, which at least $2$ and up to $50$ unique names. Each name is a string of up to $15$ letters (using only a–z and A–Z), and names are separated by single spaces. All students go by their first names only since none of them share the same first name. Input ends at end of file.

Output

For each risk assessment, the person named $a$ needs to pass a secret to the person named $b$. Determine the minimum risk path for passing a secret from $a$ to $b$. Output the value of the minimum risk followed by the sequence of people the message must traverse. If there is no way to pass a message from $a$ to $b$, simply print out the word “impossible” on a line by itself. If there are multiple minimum risk ways to pass the note, report any one of them.

alice bob
4
alice eve delmar
sandi eve trevor rudolf lucy
eve bret julia
lucy bret bob
sam jasper
1
lorenzo wesley bobby
bill ted
3
ted brianna wanda bill
alice bill
alice ted

5 alice eve bret bob
impossible
1 bill alice ted