#include <stdio.h>
#include <strings.h>


typedef struct {
	int svetla, kde, vzd;
} Stav;

static int R,D,S;
static int A[20][20];
static int B[20][20];
static Stav F[100000];
static int l,r;

static int was[10000][30];

void f_init(void) {l=r=0;}
void f_put(Stav x) { 
	if (was[x.svetla][x.kde]) return;
	F[r++]=x;
	was[x.svetla][x.kde]=1;
}

Stav f_get(void) { return F[l++]; };
int f_empty(void) {return l>=r;}

int is(int svetla, int kde) {
	return (1<<kde) & svetla;
}
int xor(int svetla, int kde) { return svetla^(1<<kde); }

int work(void)
{
	Stav x,y;
	int i;

	f_init();
	x.vzd=0; x.svetla=1; x.kde=0;
	f_put(x);
	while (!f_empty()) {
		x=f_get();

		//nie sme nahodou hotovi?
		if (x.kde==R-1 && x.svetla==(1<<(R-1)) ) {
			printf("Mr. Black needs %d steps.\n",x.vzd);
			return 0;
		}

		x.vzd++;
		
		for (i=0; i<R; i++) {
			if (i==x.kde) continue;
			if (!B[x.kde][i]) continue;
			y=x; y.svetla=xor(y.svetla,i); f_put(y);
		}
		for (i=0; i<R; i++) {
			if (!A[x.kde][i]) continue;
			if (!is(x.svetla,i)) continue;
			y=x; y.kde=i; f_put(y);
		}
	}
	printf("Poor Mr. Black! No sleep tonight!\n");
	return 0;
}
int main()
{
	int i;
	while(1)
	{
		scanf("%d %d %d ", &R, &D, &S);
		if (R==0 && D==0 && S==0) break;
		bzero(A,sizeof(A)); 
		bzero(B,sizeof(B)); 
		for (i=0; i<D; i++) {
			int x,y;
			scanf("%d %d ",&x, &y);
			A[x-1][y-1]=1;
			A[y-1][x-1]=1;
		}
		for (i=0; i<S; i++) {
			int x,y;
			scanf("%d %d ",&x, &y);
			B[x-1][y-1]=1;
		}
		bzero(was,sizeof(was));
		work();

	}

	return 0;
}