수상한 저택

블랙 씨는 커다란 저택에 혼자 산다. 이 저택의 전기 배선은 특이해서, 많은 전등 스위치가 스위치가 놓인 방이 아니라 다른 방의 전등을 제어한다.

늦은 밤 집에 돌아온 블랙 씨는 현관에 서 있고, 이때 현관을 제외한 모든 방의 불은 꺼져 있다. 그는 어둠을 무서워하기 때문에 다음 두 규칙을 반드시 지킨다.

• 불이 꺼진 방에는 절대 들어가지 않는다.
• 지금 자신이 있는 방의 불은 절대 끄지 않는다.

블랙 씨는 침실에 도착하면서, 마지막에는 침실 불만 켜져 있고 나머지 모든 불은 꺼진 상태로 만들고 싶어 한다.

저택에는 $1$번부터 $R$번까지 번호가 매겨진 $R$개의 방이 있다. $1$번 방은 현관, $R$번 방은 침실이다. 방들은 문으로 연결되어 있으며, 각 스위치는 어떤 방에 놓여 있고 (같은 방일 수도 있는) 어떤 방의 불을 제어한다.

현관 불만 켜진 채 현관에서 출발하여, 블랙 씨가 침실에 있고 오직 침실 불만 켜져 있게 만드는 행동의 순서를 구하라. 다음 각각을 한 걸음으로 센다.

• 문을 통해 이웃한 방으로 이동하기
• 불 켜기
• 불 끄기

가능한 모든 방법 중 걸음 수의 최솟값을 출력하라.

입력은 여러 개의 저택 정보로 이루어진다.

각 저택은 세 정수 $R$, $D$, $S$ ($1 \le R \le 10$)가 적힌 줄로 시작한다. $R$은 방의 수, $D$는 문의 수, $S$는 스위치의 수이다.

이어지는 $D$개의 줄에는 각각 두 정수 $I$와 $J$가 있으며, $I$번 방과 $J$번 방이 문으로 연결되어 있음을 뜻한다.

그다음 $S$개의 줄에는 각각 두 정수 $K$와 $L$이 있으며, $K$번 방에 $L$번 방의 불을 제어하는 스위치가 있음을 뜻한다.

각 저택 정보 사이는 빈 줄로 구분된다. 입력은 $R = D = S = 0$인 저택으로 끝나며, 이 저택은 처리하지 않는다.

각 저택마다 한 줄을 출력한다.

블랙 씨가 성공할 수 있다면 다음을 출력한다.

Mr. Black needs X steps.

여기서 $X$는 침실에 도착하여 침실 불만 남기는 데 필요한 최소 걸음 수이다.

불가능하다면 다음을 출력한다.

Poor Mr. Black! No sleep tonight!