题目描述
一个人买了一栋别墅，有r（r<=10）个房间，d条房间通道，l个灯的开关，告诉了哪两个房间是连通的，又有哪些灯的开关在哪个屋子里，这个人要从房间1到房间r，但是他怕黑，如果要进的屋子是黑的就不进去，问给出的条件是否能让他顺利从1到 r并且除r之外所有灯都是灭的，如果可以输出开灯，关灯的移动的步骤。
输入描述
输入包含多个别墅描述。每个别墅描述第一行包含三个整数r，d和s。 r是别墅的房间数量，最多10个,d是房间通道的数量，r是别墅中的灯开关数量。
这一行后跟d行，每行包含两个整数i和j，表示房间i和j之间有通道（房间编号从1到r）。接下来的s行每行包含两个整数k和l，表示在房间k有一个灯开关控制房间l的灯。
空白行将别墅描述与下一个描述分开。
输入以r = d = s = 0结束。
输出描述
对于每个别墅，首先输出测试用例的编号（比如“Villa＃1”，“Villa＃2”'等）。
如果有解决方案，请输出尽可能短的步骤（如果找到多个仅输出一个最短的）。
遵循下面示例中显示的【输出格式】。
如果没有解决方案，则输出一行包含“The problem cannot be solved.”。
在每个测试用例后输出一个空行。
样例输入
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
样例输出
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.
提示
