#include <stdio.h>

int state[11 << 16];
int path[11][11];
int sw[11][11];
int fronta[11 << 16];
int head,tail, final;
int r;


void add(int par) {
  int location = par >> 16;
  int stav = par & 0xFFFF;
  int n, i;
  /* prechod */
  for(i = 1; i < r+1; i++) {
    if (path[location][i] && stav & (1 << i-1)) {
      n = (i << 16) | stav;
      if (!state[n]) {
	fronta[tail++] = n;
	state[n] = 1;
      }
    }
  } 
  /* switch */
  for(i = 1; i < r+1; i++) {
    if (i == location) continue;
    if (sw[location][i]) {
      n = (location << 16) | (stav ^ (1 << i-1)) ;
      if (!state[n]) {
	fronta[tail++] = n;
	state[n] = 1;
	
      }
    }
  }
}

int main(void) {
  int d,s, i, a,b, step;
  for(;;) {
    scanf("%d%d%d",&r,&d,&s);
    if (r == 0 && d == 0 && s == 0) break;
    for(i = 0; i <= r; i++) {
      for(a = 0; a <= r; a++) {
	path[i][a] = 0;
	sw[i][a] = 0;
      }
    }
    for (i = 0; i <= r; i++)
      {
	for (a = 0; a < (1 << 10); a++)
	  state[(i << 16)|a] = 0;
      }
    for(i = 0; i < d; i++) {
      scanf("%d%d",&a,&b);
      path[a][b] = 1;
      path[b][a] = 1;
    } 
    for(i = 0; i < s; i++) {
      scanf("%d%d",&a,&b);
      sw[a][b] = 1;
    }
    fronta[0] = (1 << 16) | 1;
    state[fronta[0]] = 1;
    final = (r << 16) | (1 << r-1) ;
      
    head = 0;
    tail = 2;
    step = 0;
    fronta[1] = 0;
    while (head != tail && fronta[head] != final) {
      if (fronta[head] == 0) {
	step++;
	head++;
	if (fronta[tail - 1] != 0)
	  fronta[tail++] = 0;
      }
      else{
      add(fronta[head]);
      head++;
      }
    }
    if (head == tail) {
      printf("Poor Mr. Black! No sleep tonight!\n");
    } else {
      printf("Mr. Black needs %d steps.\n",step);
    }
  }
  return 0;
}