UVA321 The New Villa

Black先生最近在乡下买了一栋别墅。只有一件事情使他烦恼：虽然在大多数房间里有电灯开关，但这些开关控制的灯通常是在其他房间的灯，而不是在自己房间里的灯。而他的房地产代理商却认为这是一个特色，Black先生则认为是电工在连接开关插座的时候，有点心不在焉（委婉地说法）。 一天晚上，Black先生回家晚了。他站在走廊上，注意到所有其他房间里的灯都是关着的。不幸的是，Black先生害怕黑暗，所以他从来不敢进入一间关着灯的房间，他也从来不会关掉他所在房间的灯。 经过一番思考后，Black先生能够使用不正确连接的电灯开关。他要设法进入他的卧室，并关掉除了卧室以外的所有的灯。 请你编写一个程序，给出别墅的描述，初始的时候只有走廊的灯是开着的，程序确定如何从走廊到卧室。你不能进入一个黑暗的房间，并在最后一步之后，除了在卧室里的灯之外，所有的灯都必须关闭。如果有若干条路径到达卧室，你必须找到一条步数最少的路径，其中“从一间房间到另一间房间”“开灯”以及“关灯”都算一步。

输入给出若干个别墅的描述。每个别墅描述的第一行给出三个整数r、d和s。其中r是别墅里的房间数，最多有10间；d是连接两间房间的门的数量；而s是别墅里灯的开关数。房间编号由1到r。编号为1的房间是走廊，编号为r的房间是卧室。 后面给出的d行，每行给出两个整数i和j，表示房间i和房间j有一扇门连接。然后给出s行，每行给出两个整数k和l，表示在房间k中有一个开关控制房间l中的灯。 在两个别墅描述之间用一个空行分隔。输入以别墅描述r = d = s = 0结束，程序对此不必处理。

对于每栋别墅，首先在一行中输出测试用例的编号（“Villa #1”，“Villa #2”，等等）。 如果Black先生的问题有解，则输出使得他进入卧室步数最少，且只有卧室的灯开着的步序列（如果你找到步序列不止一个，仅输出一条最短的步序列）。请按照样例给出的输出个数输出。 如果没有解，输出一行“The problem cannot be solved.”。 在每个测试用例之后，输出一个空行。