Mysterious Villa

Mr. Black lives alone in a large villa. Its wiring is unusual: many light switches control the lights of rooms other than the room that holds the switch.

When Mr. Black comes home late at night he is standing in the hallway, and every light except the hallway light is off. He is afraid of the dark, so he always obeys two rules:

• he never enters a room whose light is off, and
• he never switches off the light of the room he is currently in.

He wants to reach his bedroom and finish with only the bedroom light on and every other light off.

The villa has $R$ rooms numbered $1$ to $R$. Room $1$ is the hallway and room $R$ is the bedroom. Rooms are joined by doors, and each switch sits in some room and controls the light of some (possibly the same) room.

Starting in the hallway with only the hallway light on, find a sequence of actions that leaves Mr. Black in the bedroom with only the bedroom light on. Each of the following counts as one step:

• moving through a door to an adjacent room,
• switching a light on,
• switching a light off.

Among all valid sequences, output the minimum possible number of steps.

The input contains several villa descriptions.

Each villa begins with a line of three integers $R$, $D$, and $S$ ($1 \le R \le 10$), where $R$ is the number of rooms, $D$ is the number of doors, and $S$ is the number of switches.

The next $D$ lines each contain two integers $I$ and $J$, meaning room $I$ and room $J$ are connected by a door.

The following $S$ lines each contain two integers $K$ and $L$, meaning there is a switch in room $K$ that controls the light of room $L$.

A blank line separates one villa description from the next. The input ends with a villa whose line is $R = D = S = 0$; that villa is not processed.

For each villa, print one line.

If Mr. Black can succeed, print

Mr. Black needs X steps.

where $X$ is the minimum number of steps that takes him to the bedroom and leaves only the bedroom light on.

If it is impossible, print

Poor Mr. Black! No sleep tonight!