#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <limits.h>

#define CODE(lights,pos) ((lights)*10+(pos))
#define LIGHTS(code) ((code)/10)
#define POS(code) ((code)%10)

#define ZERO(x) (memset((x),0,sizeof(x)))

static int steps[(2<<10)*10];
static int steps_best;
static int todo[(2<<10)*10+100];
static int todoN;
static int Switch[10][10];
static int door[10][10];


static void go(int code,int stepped)
{
	if (steps[code] && steps[code]<=stepped)
		return;
	steps[code]=stepped;
	todo[todoN++]=code;
}

int main(void)
{
int i,R,D,S,s,d,I,J,K,L,r;

	for (;;) {
		i=scanf("%d %d %d\n",&R,&D,&S);
		assert(i==3);
		if (R==0 && D==0 && S==0)
			break;
		ZERO(steps);
		ZERO(todo);
		ZERO(Switch);
		ZERO(door);
		steps_best=INT_MAX;
		todoN=0;
		for (d=0;d<D;d++) {
			i=scanf("%d %d\n",&I,&J);
			assert(i==2);
			assert(I>=1 && I<=R);
			I--;
			assert(J>=1 && J<=R);
			J--;
			door[I][J]=1;
			door[J][I]=1;
			}
		for (s=0;s<S;s++) {
			i=scanf("%d %d\n",&K,&L);
			assert(i==2);
			assert(K>=1 && K<=R);
			K--;
			assert(L>=1 && L<=R);
			L--;
			Switch[K][L]=1;
			}
		go(CODE(1<<0,0),1);
		while (todoN) {
int code=todo[--todoN];
int lights=LIGHTS(code),pos=POS(code);
int stepped=steps[code];

			for (r=0;r<R;r++) {
				if (!Switch[pos][r])
					continue;
				if (pos==r)
					continue;
				go(CODE(lights^(1<<r),pos),stepped+1);
				}
			for (r=0;r<R;r++) {
				if (!door[pos][r])
					continue;
				if (!(lights & (1<<r)))
					continue;
				go(CODE(lights,r),stepped+1);
				}
			}
		if (!steps[CODE(1<<(R-1),R-1)])
			puts("Poor Mr. Black! No sleep tonight!");
		else
			printf("Mr. Black needs %d steps.\n",
					steps[CODE(1<<(R-1),R-1)]-1);
		}
	return 0;
}