#include <stdio.h>
#include <stdlib.h>

#define SWITCH_LIGHT(l,p) ((l)^(1<<(p)))
#define LIGHT_ON(l,p) ((l)&(1<<p))
#define MAZE(x) ((x)>>10)
#define LIGHTS(x) ((x) &((1<<10)-1))
#define STATE(m,l) (((m) << 10) | (l))

int dists[20*(1<<10)];
int frontaA[20*(1<<10)];
int frontaB[20*(1<<10)];
int frontaC[20*(1<<10)];
int *fronta,*fronta1,*fronta2;
int fpos,fend,fend1,fend2;

int switches[10][10];
int doors[10][10];

int R,D,S;

int main() {

  int i,j,a,b;
  int s,c,d;

  while (1) {
    scanf("%d%d%d",&R,&D,&S);
    if (!R)
      return 0;

    for (i = 0; i < R; i++)
      for (j = 0;j < R; j++)
        switches[i][j] = doors[i][j] = 0;

    for (i = 0; i <D; i++) {
      scanf("%d%d",&a,&b);
      a--;b--;
      doors[a][b] = 1;
      doors[b][a] = 1;
    }

    for (i = 0; i < S; i++) {
      scanf("%d%d",&a,&b);
      a--;b--;
      switches[a][b] = 1;
    }

    s = STATE(0,SWITCH_LIGHT(0,0));
    c = STATE(R-1,SWITCH_LIGHT(0,R-1));

    for (i = 0; i < 10*(1<<10); i++)
      dists[i] = -1;

    fronta = frontaA;
    fronta1 = frontaB;
    fronta2 = frontaC;

    fend1 = 1;
    fronta1[0] = s;
    dists[s] = 0;

    while (fend1 || fend2) {
      int *xxx = fronta;
      fronta = fronta1;
      fronta1 = fronta2;
      fronta2 = xxx;
      fpos = 0;
      fend = fend1;
      fend1 = fend2;
      fend2 = 0;

      while (fpos < fend) {
        int x = fronta[fpos++];
        int m = MAZE(x);
        int l = LIGHTS(x);
        int d = dists[x];

        for (i = 0; i < R; i++) 
          if (switches[m][i] && i!=m) {
            int n = STATE(m,SWITCH_LIGHT(l,i));
            if (dists[n] < 0 || dists[n] > d + 1) {
              dists[n] = d + 1;
              fronta1[fend1++] = n;
            }
          }

        for (i = 0; i < R; i++)
          if (doors[m][i]) {
            if (LIGHT_ON(l,i)) {
              int n = STATE(i,l);
              if (dists[n] < 0 || dists[n] > d + 1) {
                dists[n] = d + 1;
                fronta1[fend1++] = n;
              }
            } else if(switches[i][i]) {
              int n = STATE(i,SWITCH_LIGHT(l,i));
              if (dists[n] < 0 || dists[n] > d + 2) {
                dists[n] = d + 2;
                fronta2[fend2++] = n;
              }
            }
          }

      } /* while fronta */
    } /* while fronty */
    
    d = dists[c];
    if (d >= 0) 
      printf("Mr. Black needs %d steps.\n",d);
    else
      printf ("Poor Mr. Black! No sleep tonight!\n");
  }
}