1323: 邹小竞老师的别墅

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：1 Solved：1

Description

邹小竞老师快要结婚了，和男朋友一起买了一个大别墅，待到装修完毕后，却遇上了一件烦恼的事情。原来，邹小竞请学生光头玲当的电工，光头玲不懂电路，一顿乱搞，虽然大多数房间里有电灯开关，但是这些开关控制的灯通常是其他房间的灯，而不是自己房间的灯。而光头玲已经卷款跑路了，工程烂尾了。

这天晚上，邹小竞回到家，她站在走廊上，注意到所有其它房间的灯都是关着的。由于邹小竞特别怕黑，所以她不敢一个人夜晚进入黑暗的房间（不巧的是邹小竞的男友陶总正在加班没回家），也不敢在夜晚关掉她所在房间的灯。

经过思考，邹小竞决定使用现有的不正确电路的电灯开关，她要设法进入她的卧室，并关掉除了卧室之外的所有的灯。

请你编写一个程序，给出别墅的描述，初始的时候只有走廊的灯是开着的，程序确定如何从走廊到卧室。你不能进入一个黑暗的房间，并在最后一步之后，除了在卧室里的灯之外，所有的灯都必须关闭。如果有若干条路径到达卧室，你必须找到一条步数最少的路径，其中，每一次“从一间房间到另一间房间”、“开灯”和“关灯”都算一步。

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

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

Output

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

Sample Input Copy 

3 3 4
1 2
1 3
3 2
1 2
1 3
2 1
3 2

2 1 2
2 1
1 1
1 2

0 0 0

Sample Output Copy 

Villa #1
The problem can be solved in 6 steps:
- Switch on light in room 2.
- Switch on light in room 3.
- Move to room 2.
- Switch off light in room 1.
- Move to room 3.
- Switch off light in room 2.

Villa #2
The problem cannot be solved.

Source/Category