#include <stdio.h>

int R;
char conn[15][15];
char ctrl[15][15];

int states[12000];

int queue[100000];
int qhead;
int qtail;

int state;
int final;

void printState(int st) {
  int room = 1 + st / 1024;
  int lights = st % 1024;
//printf("state=%d, room=%d, lights=%d", state, room, lights); 
}

void addState(int state, int steps) {
//printf("addState(");
//printState(state);
//printf("steps=%d)\n", steps);
	if (!states[state]) {
		states[state] = steps;
		queue[qtail++] = state;
	}
}


void go() {
	while (qhead != qtail) {
		state = queue[qhead++];
		if (state == final) break;
		int room = 1 + state / 1024;
		int lights = state % 1024;
		int stp = states[state];
//printf("state=%d, room=%d, lights=%d, stp=%d\n", state, room, lights, stp); 
		for (int i=1; i<=R; i++) { // go to other room
			if (conn[room][i] && (lights & (1<<(i-1)))) {
				addState((i-1)*1024 + lights, stp+1);
			}
		}

		for (int i = 1; i<=R; i++) { // change lights
			if (ctrl[room][i] && i != room) { // can control i's light
				addState(state ^ (1<<(i-1)), stp+1);	
			}
		}
	}
}


void cleanup(void) {
	for (int i=0; i<15; i++) {
		for (int j=0; j<15; j++) {
			conn[i][j] = 0;
			ctrl[i][j] = 0;
		}
	}
	for (int i=0; i<12000; i++) states[i] = 0;
}


int main(void) {
    int s, d;
    int from, to;

    for (;;) {
	cleanup();
	scanf ("%d %d %d\n", &R, &d, &s);
	if( R == 0 ) break;
	
	while (d--) { // parse doors
		scanf("%d %d\n", &from, &to);
		conn[from][to] = 1;
		conn[to][from] = 1;
	}

	while (s--) { // parse switches
		scanf("%d %d\n", &from, &to);
		ctrl[from][to] = 1;
	}

	qtail = 1;
	qhead = 0;
	state = 1;
	final = 1024*(R-1) + (1 << (R-1));
	queue[0] = 1; // initial state
	states[1] = 1; // steps+1 to reach

//printf("final=%d\n", final);

	go();
	if (state == final) {
		printf("Mr. Black needs %d steps.\n", states[final]-1);
	} else {
		printf("Poor Mr. Black! No sleep tonight!\n");
	}
    }

    return 0;
}