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

#define LENGTH(x) (sizeof(x)/sizeof(*(x)))

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

static int marked[(2<<10)*10];
static int steps[(2<<10)*10];
static int todo[(2<<10)*10+100];
static int todoB,todoE;
static int Switch[10][10];
static int door[10][10];
static int round=1;

#define NDEBUG 1

#define go(code,stepped) do { \
		if (marked[(code)]!=round || steps[(code)]>(stepped)) { \
			marked[(code)]=round; \
			steps[(code)]=(stepped); \
			todo[todoE++]=(code); \
			todoE%=LENGTH(todo); \
			} \
		} while (0)

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

	for (;;) {
		round++;
		i=scanf("%d %d %d\n",&R,&D,&S);
		assert(i==3);
		if (R==0 && D==0 && S==0)
			break;
		todoB=todoE=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]=round;
			door[J][I]=round;
			}
		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]=round;
			}
		go(CODE(1<<0,0),1);
		while (todoB!=todoE) {
int code=todo[todoB++];
int lights=LIGHTS(code),pos=POS(code);
int stepped=steps[code];

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