题目描述

布莱克先生最近在乡下买了一栋别墅。唯一让他困扰的一件事是：尽管大多数房间都有电灯开关，但这些开关所控制的灯却常常在其他房间。他的房产经纪人认为这是一个特色，但布莱克先生却开始觉得，电工在连接开关和插座时有点心不在焉（说得委婉一点）。

一天晚上，布莱克先生回家很晚。站在走廊里时，他注意到其他所有房间的灯都是关着的。不幸的是，布莱克先生怕黑，所以他从来不敢进入灯是关着的房间，并且也绝不会关掉自己所在房间的灯。

经过一番思考，布莱克先生能够利用这些接错线的电灯开关为自己服务。他成功地到达了自己的卧室，并且关掉了除卧室灯之外的所有灯。

你需要编写一个程序，给定别墅的描述，确定在只有走廊的灯最初是开着的情况下，如何从走廊到达卧室。你绝不能进入黑暗的房间，并且在最后一步之后，除了卧室的灯之外，所有灯都必须是关掉的。如果有几条通往卧室的路径，你必须找到使用步数最少的那一条，其中 “从一个房间移动到另一个房间”、“打开一盏灯” 和 “关掉一盏灯” 都算作一步。

输入格式

输入文件包含多个别墅的描述。每个别墅的描述以一行开头，该行包含三个整数 $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” 等）。

如果布莱克先生的问题有解决方案，输出能使他到达卧室并且只留下卧室灯亮着的最短步骤序列。（如果找到多个最短序列，只输出其中一个）。请遵循下面示例中显示的输出格式。

如果没有解决方案，输出一行包含语句 “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.

来源

1996年西南欧洲区域竞赛