测试数据来自 wjszez/2074

布莱克先生是土尔其总统的顾问，因此他也将前往参加北约峰会。他喜欢单独居住，远离商业中心的宾馆。于是他在奥瑞契佛加租了一间大的别墅。但有一件事搅扰了他：尽管大多数的房间都有电灯开关，但这些开关经常只能控制其它房间的灯而不是自己房间的。但是房产经纪人却认为这是一个特色，布莱克先生只能认为当电工们将开关连接到框架上时，他们是心不在焉的。
有些夜晚，布莱克先生回来的很晚，当他站在门厅中时，所有其它房间的灯都是关的。因为布莱克先生怕黑，所以他不敢进入黑暗的房间，也不敢关掉他所在房间的灯。布莱克先生想利用这些接错位置的开关帮助他前进。他希望能走到卧室并关掉卧室以外所有的灯。
编写程序，根据给定的房间说明，考虑当仅有门厅中亮的时候，你如何从门厅到卧室。不可以进入一个黑暗的房间，只能在房间中关自己房间的开关，最后时，除了卧室以外的灯其余的灯都必须关闭，每个房间都只有一盏灯。如果有几种办法可以通往卧室，你必须找出使用步数最少的方法。其中“从一个房间到另一个房间”，“开灯”和“关灯”每个过程算一步。

输入
输入文件第一行包含三个整数R，D和S。R表示别墅的房间数，1<=R<=10,D表示房间之间连接的门数，S表示别墅中灯的开关数。房间用数字1到R标识，1号房间表示门厅，R房间表示卧室。接下来的D行每行包含两个整数I和J，表示房间I和房间J之间有一扇门连接。接下来的S行每行包含两个整数K和L，表示房间K中有一个开关控制房间L中的电灯。

输出
输出一行解。如果对于布莱克先生有解，则输出“Mr.Black needs X Steps.”其中X表示来到他的卧室并将所有其它房间的灯关掉所需的最少步数。如果无解，输出“Poor Mr. Black! No sleep tonight!”

样例
VILLA.IN
3 3 4
1 2
1 3
3 2
1 2
1 3
2 1
3 2

VILLA.OUT
Mr. Black needs 6 steps.