Time Limit: Java: 2000 ms / Others: 2000 ms
Memory Limit: Java: 65536 KB / Others: 65536 KB
One night, Mr. Black came home late. While standing in the hallway, he noted that the lights in all other rooms were switched off. Unfortunately, Mr. Black was afraid of the dark, so he never dared to enter a room that had its lights out and would never switch off the lights of the room he was in.
After some thought, Mr. Black was able to use the incorrectly wired light switches to his advantage. He managed to get to his bedroom and to switch off all lights except for the one in the bedroom.
You are to write a program that, given a description of a villa, determines how to get from the hallway to the bedroom if only the hallway light is initially switched on. You may never enter a dark room, and after the last move, all lights except for the one in the bedroom must be switched off. If there are several paths to the bedroom, you have to find the one which uses the smallest number of steps, where ``move from one room to another'', ``switch on a light'' and ``switch off a light'' each count as one step.
This line is followed by d lines containing two integers i and j each, specifying that room i is connected to room j by a door. Then follow s lines containing two integers k and l each, indicating that there is a light switch in room k that controls the light in room l.
A blank line separates the villa description from the next one. The input ends with a villa having r = d = s = 0, which should not be processed.
If there is a solution to Mr. Black's problem, output the shortest possible sequence of steps that leads him to his bedroom and only leaves the bedroom light switched on. (Output only one shortest sequence if you find more than one.) Adhere to the output format shown in the sample below.
If there is no solution, output a line containing the statement `The problem cannot be solved.'
Output a blank line after each test case.
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.