{
  CTU Open Contest 2002
  =====================
  Sample solution for the problem: villa

  Martin Kacer, Oct 2002
}

Program Villa;

Const MAXROOM = 10;
	MAXCOMB = 1024;
	INFINITY = 1000000;

{ pos = where is Mr. Black; lights = state of lights (0..2^10-1) }
Type TState = Record pos: Integer; lights: Integer; End;

Var Space : Array [1..MAXROOM, 0..(MAXCOMB-1)] of Integer;
	Door : Array [1..MAXROOM, 1..MAXROOM] of Boolean;
	Light : Array [1..MAXROOM, 1..MAXROOM] of Boolean;
	Queue : Array [1..MAXROOM * MAXCOMB] of TState;
	QB, QE : Integer;


{ bit that represents n-th room }
Function GetBit (N: Integer) : Integer;
Begin
	GetBit := 1 shl (N-1);
End; { GetBit }


{ initialize the data structures }
Procedure ClearAll;
Var I, J: Integer;
Begin
	For I := 1 to MAXROOM do
		For J := 0 to MAXCOMB-1 do
			Space[I,J] := INFINITY;
	For I := 1 to MAXROOM do
		For J := 1 to MAXROOM do
		Begin
			Door[I,J] := false;
			Light[I,J] := false;
		End;
	QB := 1; QE := 1;
End;


{put the state into the queue if it has not been already visited}
Procedure EnqueueState (S: TState; C: Integer);
Begin
	If Space[S.pos, S.lights] > C then
	Begin
		Space[S.pos, S.lights] := C;
		Queue[QE] := S;
		Inc (QE);
	End;
End;


{try all possible moves from the given state}
Procedure ExpandState (S: TState);
Var I, C: Integer;
	SX: TState;
Begin
	C := Space[S.pos, S.lights];
	For I := 1 to MAXROOM do
		if Door[S.pos, I] and ((S.lights and GetBit(I)) <> 0) then
		Begin
			SX := S;
			SX.pos := I;
			EnqueueState (SX, C+1);
		End;
	For I := 1 to MAXROOM do
		If Light[S.pos, I] and (I<>S.pos) then
		Begin
			S.lights := S.lights xor GetBit(I);
			EnqueueState (S, C+1);
			S.lights := S.lights xor GetBit(I);
		End;
End;


{find all possible paths - completely solve one problem}
Function SolveOne (R: Integer) : Integer;
Var S: TState;
Begin
	S.pos := 1;
	S.lights := GetBit (1);
	EnqueueState (S, 0);
	While (QB < QE) and (Space [R, GetBit(R)] = INFINITY) do
	Begin
		ExpandState (Queue[QB]);
		Inc (QB);
	End;
	SolveOne := Space [R, GetBit(R)];
End;


Var R, D, S: Integer;
	I, X, Y: Integer;

Begin
	Repeat
		ReadLn (R, D, S);
		If (R > 0) then
		Begin
			ClearAll;
			For I := 1 to D do
			Begin
				ReadLn (X, Y);
				Door[X,Y] := true;
				Door[Y,X] := true;
			End;
			For I := 1 to S do
			Begin
				ReadLn (X, Y);
				Light[X,Y] := true;
			End;
			X := SolveOne (R);
			If (X < INFINITY) then
				WriteLn ('Mr. Black needs ',X,' steps.')
			else
				WriteLn ('Poor Mr. Black! No sleep tonight!');
		End;
	Until (R = 0);
End.

