Background

Special for beginners, ^_^

Description

农夫约翰靠着奶牛攒够了首付，终于搬入了他新购买的别墅中，为了能早日还清房贷，本着能省就省的原则，装修时找了马路上的游击队，三脚猫的电工乱接线，导致一个房间内的开关实际控制的可能是另一个房间的灯。

一天晚上，农夫约翰很晚才到家。农夫约翰在卖奶时经常以次充好，把过期的牛奶重新打个日期卖出去。做了亏心事，当然怕鬼敲门，所以他非常怕黑。他不敢进入不亮灯的房间，也不敢把他所在房间的灯关了。

约翰想，有没有可能有一种行进路线和开关灯的方式，让他能从门口进入他的卧室，并且最后除了卧室的灯，别的灯全部关闭。

你现在的任务就是写一个程序，初始时只有门口的灯是亮的，不进入不亮灯的房间，并且最后进入卧室，并关闭除了卧室以外的所有灯。如果有多种进入卧室的方式，必须用最快的方式，假设从一个房间进入另一个房间、打开灯，关闭灯分别需要1秒。

Format

Input

输入包含多个测试例。

每个测试例的第一行给出三个数，r、d、s，分别表示别墅的房间数（不超过10），连接房间之间的门数，别墅的灯数。房间编号从1到r，房间1是门口，房间r是卧室。 接下来d行，每行给出每扇门所连接的两个房间的编号。 最后的s行，每行给出两个数k和l，表示房间k的开关控制的是房间l的灯。

每个测试例之间有个空行，如果输入r = d = s = 0表示输入结束，无需处理。

Output

对每个测试例，首先在一行中输出序号，即（“Villa #1”, “Villa #2”,）。

如果有多个解，则输出最短的步骤使得约翰进入卧室并关闭除卧室以外的其他所有灯。格式输出参考下面的样例。 如果还是有多个解，输出最小字典序的解。

如果无解，则输出“The problem cannot be solved.”。

每个测试例后输出一个空行。

Samples

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.

Limitation

1s, 1024KiB for each test case.