#include <stdio.h>
#define N 1100
#define M 11

int stav[N][M];
int r,d,s;
int p[M][M];
int sw[M][M];

int q[N*M][2];
int qhead,qtail;

int f(int c, int room)
{
  int i;
  int cc=c;
  int za[M];
  
  for ( i=0; i<M; i++ )
  {
    if (cc%2==1) za[i]=1; else za[i]=0;
    cc/=2;
  }

  for ( i=0; i<r; i++ )
    if (za[i] && p[room][i])
    {
      if (stav[c][i]==0) {q[qhead][0]=c; q[qhead][1]=i; qhead++;
       stav[c][i]=stav[c][room]+1;}
    }
  
  for ( i=0; i<r; i++ ) if (sw[room][i] && i!=room)
  {
    cc=c ^ (1<<i);
    if (stav[cc][room]==0) {q[qhead][0]=cc; q[qhead][1]=room; qhead++;
     stav[cc][room]=stav[c][room]+1;}
  }
  
  return 0;
}

int main()
{
  int i,j,p1,p2;

  while (1)
  {
    scanf("%d %d %d", &r, &d, &s); if (!r && !s && !d) break;
    for ( i=0; i<r; i++ ) for ( j=0; j<r; j++ ) p[i][j]=sw[i][j]=0;
    for ( i=0; i<d; i++ )
    { 
      scanf("%d %d", &p1, &p2); p1--; p2--;
      p[p1][p2]=1; p[p2][p1]=1;
    }
    for ( i=0; i<s; i++ )
    { 
      scanf("%d %d", &p1, &p2); p1--; p2--;
      sw[p1][p2]=1;
    }

    for ( i=0; i<N; i++ ) for ( j=0; j<M; j++ ) stav[i][j]=0;
    stav[1][0]=1; qhead=1; qtail=0; q[0][0]=1; q[0][1]=0;
    
    while (qhead>qtail && stav[1<<(r-1)][r-1]==0)
    {
      f(q[qtail][0],q[qtail][1]);
      qtail++;
    } 
    if (stav[1<<(r-1)][r-1]==0) 
      printf("Poor Mr. Black! No sleep tonight!\n");
    else printf("Mr. Black needs %d steps.\n", stav[1<<(r-1)][r-1]-1);
  }

  return 0;
}