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

#define N 11

int D[N][N];
int S[N][N];
int T[N<<N];
int fr,fw,F[N<<N];
int n;
  
int find() {
  int i,act,next;
  
  fr=0; fw=1;
  F[0]=1;
  T[1]=0;
  while (fr!=fw) {
    act=F[fr]>>N;
    
    if (F[fr] == ( ( (n-1)<<N) | (1 <<(n-1) ))  ) return T[F[fr]];
    for (i=0;i<n;i++) 
      if (D[act][i]) 
        if (F[fr] & (1<<i)) {
          next=( F[fr] & ((1<<N)-1) ) | (i<<N);
          if (T[next]==-1) {
            T[next]=T[F[fr]]+1;
            F[fw]=next;
            //   printf("next=%d %d, s=%d\n",next>>N,next & ( (1<<N)-1 ), T[F[fr]]+1);
            fw++;
          }
        }
    for (i=0;i<n;i++) 
      if (S[act][i]) 
        if (i!=act) {
          next=F[fr] ^ (1<<i);
          if (T[next]==-1) {
            T[next]=T[F[fr]]+1;
            F[fw]=next;
            fw++;
          }
        }
    fr++;      
  }
  return -1;
}

int main() {
  int i,s,d,a,b;
  while(1) {
    scanf("%d %d %d ",&n,&d,&s);
    if (n==0) break;
    memset(D,0,sizeof(D));
    memset(S,0,sizeof(S));
    memset(T,-1,sizeof(T));
    for (i=0;i<d;i++) {
      scanf("%d %d ",&a,&b);
      a--;b--;
      D[a][b]=D[b][a]=1;
    }
    for (i=0;i<s;i++) {
      scanf("%d %d ",&a,&b);
      a--;b--;
      S[a][b]=1;
    }
      
    i=find();
    if (i==-1) printf("Poor Mr. Black! No sleep tonight!\n");
    else printf("Mr. Black needs %d steps.\n",i);
  }
  
  return 0;
}