Doctor's Research Rooms

Dr. Tsuruga of the University of Aizu is famous for his enthusiastic research. There are several students in his lab, but he works late into the night every day, so he always comes home last. His lab has multiple rooms connected by doors, and the last person to leave the lab is supposed to turn off the lights in all the rooms and go home.

Recently, the university is focusing on energy saving, so it is strictly checked whether all the lights are off. The trouble is that he is an undisputed extreme coward who can never enter a darkened room. Therefore, he modified the lighting equipment in the laboratory so that the lighting in one room could be turned on and off from another room.

However, due to budget constraints, the number of rooms that can be controlled from one room is limited. In addition, the lighting conditions in each room when returning home vary from day to day, so it takes a considerable amount of time every day to turn off all the lights and reach the exit. So, as a researcher, you decided to create a program to help the doctor.

Create a program that inputs the room information of the laboratory, the lighting information of each room, and the lighting switch information of each room, and outputs whether the doctor can turn off all the lights and go home. However, the number of rooms n is an integer from 1 to 15 and the number of doors m is an integer from 1 to 30. It is assumed that numbers are assigned by integers greater than or equal to n or less. The exit is in room number n and the doctor always starts in room 1.

The output is divided into the following three types according to the action to be taken by the doctor.

Case 1. When all lights except the exit are turned off to reach the exit (you may pass through the exit in the process of the route).

You can go home in X steps.

Is output. Here, X is the shortest number of steps to reach the exit from the doctor's room when moving the room and turning the switch on / off as one step each. In addition, the route from the doctor's room to the exit (the action that the doctor should take) is output in X lines according to the following character string.

• When moving to room R

Move to room R.

• When turning off the lights in Room R

Switch off room R.

• When turning on the lights in Room R

Switch on room R.

Where R represents the room number. Immediately after moving to a room with a doctor, if you operate multiple switches to move to the next room, output from the one with the smallest room number to operate. As long as this condition is met, if there are multiple solutions, any one can be output. With this information, the doctor can return home safely.

Case 2. If you can reach the exit but cannot turn off all the lights except the room with the exit.

You can not switch off all lights.

Is output. In this case, the doctor will be punished by the university for failing to save energy.

Case 3. If you can't reach the exit no matter what.

Help me!

Is output. In this case, the doctor asks the guards for emergency help.

Here is a simple example. In this example, the lab consists of four rooms, with rooms 1 and 2, 2 and 3, and 2 and 4, respectively. You can also control the lights in rooms 2 and 3 from rooms 1 and 4, and you can control the lights in rooms 1, 2 and 4 from room 3. Initially, the doctor is in room 1 with the lights in rooms 2, 3 and 4 turned off.

In this situation, the actions the doctor should take are:

Turn on the lights in rooms 2 and 3. Move to room 2. Move to room 3. Turn off the lights in room 1 and turn on the lights in room 4. Move to room 2. Move to room 4. Turn off the lights in rooms 2 and 3.

The doctor can now turn off the lights outside Room 4 and go home.

Input

A sequence of multiple datasets is given as input. The end of the input is indicated by two lines of zeros. Each dataset is given in the following format:

n m s1 t1 s2 t2 :: sm tm l1 l2 ... ln k1 r1 r2 ... rk1 k2 r1 r2 ... rk2 :: kn r1 r2 ... rkn

The number of rooms n (1 ≤ n ≤ 15) and the number of doors m (1 ≤ m ≤ 30) are given on the first line, separated by blanks. The next m line gives information about the i-th door. si ti means that room si and room ti are connected by a door.

On the next line, the lighting information li (0 or 1) for room i is given, separated by blanks.

The next n lines give the switch information for room i. ki (0 ≤ ki ≤ 12) is the number of switches in room i, and r1 ... rki is the number of rooms where the lights can be manipulated.

The number of datasets does not exceed 100.

Output

For each data set, output in the following format according to the above three results.

For case 1

Line 1: You can go home in X steps. Line 2: Actions the first doctor should take Line 3: Actions the second doctor should take :: Line X + 1: Actions to be taken by the Xth doctor

In case 2

Line 1: You can not switch off all lights.

In case 3

Line 1: Help me!

Example

Input

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

Output

You can go home in 10 steps. Switch on room 2. Switch on room 3. Move to room 2. Move to room 3. Switch off room 1. Switch on room 4. Move to room 2. Move to room 4. Switch off room 2. Switch off room 3. You can not switch off all lights. Help me!

inputFormat

inputs the room information of the laboratory, the lighting information of each room, and the lighting switch information of each room, and

outputFormat

outputs whether the doctor can turn off all the lights and go home. However, the number of rooms n is an integer from 1 to 15 and the number of doors m is an integer from 1 to 30. It is assumed that numbers are assigned by integers greater than or equal to n or less. The exit is in room number n and the doctor always starts in room 1.

The output is divided into the following three types according to the action to be taken by the doctor.

Case 1. When all lights except the exit are turned off to reach the exit (you may pass through the exit in the process of the route).

You can go home in X steps.

Is output. Here, X is the shortest number of steps to reach the exit from the doctor's room when moving the room and turning the switch on / off as one step each. In addition, the route from the doctor's room to the exit (the action that the doctor should take) is output in X lines according to the following character string.

• When moving to room R

Move to room R.

• When turning off the lights in Room R

Switch off room R.

• When turning on the lights in Room R

Switch on room R.

Where R represents the room number. Immediately after moving to a room with a doctor, if you operate multiple switches to move to the next room, output from the one with the smallest room number to operate. As long as this condition is met, if there are multiple solutions, any one can be output. With this information, the doctor can return home safely.

Case 2. If you can reach the exit but cannot turn off all the lights except the room with the exit.

You can not switch off all lights.

Is output. In this case, the doctor will be punished by the university for failing to save energy.

Case 3. If you can't reach the exit no matter what.

Help me!

Is output. In this case, the doctor asks the guards for emergency help.

Here is a simple example. In this example, the lab consists of four rooms, with rooms 1 and 2, 2 and 3, and 2 and 4, respectively. You can also control the lights in rooms 2 and 3 from rooms 1 and 4, and you can control the lights in rooms 1, 2 and 4 from room 3. Initially, the doctor is in room 1 with the lights in rooms 2, 3 and 4 turned off.

In this situation, the actions the doctor should take are:

Turn on the lights in rooms 2 and 3. Move to room 2. Move to room 3. Turn off the lights in room 1 and turn on the lights in room 4. Move to room 2. Move to room 4. Turn off the lights in rooms 2 and 3.

The doctor can now turn off the lights outside Room 4 and go home.

Input

A sequence of multiple datasets is given as input. The end of the input is indicated by two lines of zeros. Each dataset is given in the following format:

n m s1 t1 s2 t2 :: sm tm l1 l2 ... ln k1 r1 r2 ... rk1 k2 r1 r2 ... rk2 :: kn r1 r2 ... rkn

The number of rooms n (1 ≤ n ≤ 15) and the number of doors m (1 ≤ m ≤ 30) are given on the first line, separated by blanks. The next m line gives information about the i-th door. si ti means that room si and room ti are connected by a door.

On the next line, the lighting information li (0 or 1) for room i is given, separated by blanks.

The next n lines give the switch information for room i. ki (0 ≤ ki ≤ 12) is the number of switches in room i, and r1 ... rki is the number of rooms where the lights can be manipulated.

The number of datasets does not exceed 100.

Output

For each data set, output in the following format according to the above three results.

For case 1

Line 1: You can go home in X steps. Line 2: Actions the first doctor should take Line 3: Actions the second doctor should take :: Line X + 1: Actions to be taken by the Xth doctor

In case 2

Line 1: You can not switch off all lights.

In case 3

Line 1: Help me!

Example

Input

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

Output

You can go home in 10 steps. Switch on room 2. Switch on room 3. Move to room 2. Move to room 3. Switch off room 1. Switch on room 4. Move to room 2. Move to room 4. Switch off room 2. Switch off room 3. You can not switch off all lights. Help me!

样例

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

You can go home in 10 steps.
Switch on room 2.
Switch on room 3.
Move to room 2.
Move to room 3.
Switch off room 1.
Switch on room 4.
Move to room 2.
Move to room 4.
Switch off room 2.
Switch off room 3.
You can not switch off all lights.
Help me!

</p>