Doctor's Research Rooms

Time Limit : 1 sec, Memory Limit : 65536 KB

Doctor's Research Rooms

会津大学の鶴賀博士はとても研究熱心なことで有名です。彼の研究室には複数の学生がいますが、彼は 毎日夜遅くまで研究をするので必ず最後に帰宅します。彼の研究室にはドアでつながった複数の部屋が あり、最後に研究室を出る人がすべての部屋の明かりを消して帰宅することになっています。最近、大 学では省エネに力を入れているため、すべての明かりが消えているか厳しくチェックされます。困った ことに彼は誰もが認める極度の臆病者で、明かりの消えた部屋には決して入ることができません。そこ で、彼はある部屋の照明のON/OFFを他の部屋から操作できるように研究室の照明設備を改造しました。 ところが、予算の都合で1つの部屋からコントロールできる部屋が限られています。その上、帰宅時の 各部屋の明かりの状態も日によって異なるため、全ての明かりを消して出口までたどりつくのに毎日か なりの時間が掛かっています。そこで、研究室で一番年下のあなたが博士を助けるためにプログラムを 作成することになりました。

研究室の部屋情報、各部屋の明かりの点灯情報、各部屋の照明スイッチの情報を入力とし、博士がすべ ての明かりを消して帰宅できるかどうかを出力するプログラムを作成してください。ただし、部屋の数 n は1以上15以下の整数、ドアの数 m は1以上30以下の整数、照明の点灯情報 i は 0 または 1 の整数 でそれぞれ消灯と点灯を表し、各部屋には1以上 n 以下の整数で番号が付与されているものとします。 出口は番号 n の部屋に存在し、博士は常に部屋 1 からスタートするものとします。

なお、出力は、博士の取るべき行動に応じて以下の3通りに分けて出力します。

ケース1. 出口以外の全ての明かりを消して出口にたどりつける場合(経路の過程で出口を通っ てもよい)。

You can go home in X steps.

と出力します。ここで X は部屋の移動、スイッチのON/OFF をそれぞれ1ステップとした場合 の、博士の部屋から出口にたどり着くまでの最短のステップ数です。さらに、以下の文字列に従 い博士の部屋から出口までの経路(博士のとるべき行動)を X 行で出力します。

  • 部屋 R へ移動する場合
    Move to room R.
    
  • 部屋 R の照明を消す場合
    Switch off room R.
    
  • 部屋 R の照明を点灯する場合
    Switch on room R.
    

ここで、Rは部屋の番号を表します。博士がある部屋に移動した直後、複数のスイッチを操作し て次の部屋に移動する場合は操作する部屋番号が小さいほうから出力してください。この条件を 満たす限り、複数の解がある場合は、どれを出力してもかまいません。 この情報をもとに、博士は無事帰宅することができます。

ケース2. 出口にたどり着くことはできるが、出口のある部屋以外の全ての明かりを消すことが できない場合。

You can not switch off all lights.

と出力する。この場合、博士は省エネを守らなかったとして大学に罰せられます。

ケース3. どうあがいても出口にたどり着けない場合。

Help me!

と出力する。この場合、博士は警備員に緊急救助を求めます。

簡単な例を示します。この例では、研究室は4つの部屋で構成され、部屋1と2、2と3、2と4がそれぞれ 繋がっています。また、部屋1及び4から部屋2、3の照明を操作することができ、部屋3から部屋1、2、4 の照明を操作することができます。最初、部屋2、3、4の照明が消えた状態で、博士が部屋1にいます。

この状況では、博士が取るべき行動は次のようになります。

部屋2と3の照明をonにする。
部屋2に移動する。
部屋3に移動する。
部屋1の照明をoffにし、部屋4の照明をonにする。
部屋2に移動する。
部屋4に移動する。
部屋2と3の照明をoffにする。

これで博士は部屋4以外の照明を消すことができ、帰宅することができます。

プログラムは以下に定義する入力が続く限り処理を繰り返し、入力が終わったら終了するように作成し てください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロ2つの行で示されます。 各データセットは以下のとおりです。

1行目 部屋の数 n ドアの数 m(整数 整数;半角空白区切り)
2行目 1個目のドアの情報 s t(整数 整数;半角空白区切り)
各記号の意味は以下の通りです。
s t :部屋 s と部屋 t がドアで繋がっている
3行目 2個目のドアの情報
4行目 3個目のドアの情報
:
:
m+1行目 m個目のドアの情報
m+2行目 照明の点灯情報 i1 i2 … in (整数 整数 …;半角空白区切り)
各記号の意味は以下の通りです。
i1:部屋の1の照明の情報
i2:部屋の2の照明の情報
:
in:部屋のnの照明の情報
m+3行目 1つ目の部屋のスイッチ情報 k r1 r2 … rk(整数 整数 …;半角空白区切り)
各記号の意味は以下の通りです。
k:スイッチの数
r1、r2、…、rk:照明を操作できる部屋番号
m+4行目 2つ目の部屋のスイッチ情報
:
:
m+n+2行目 n個目の部屋のスイッチ情報

Output

入力データセットごとに、上記の3通りの結果に応じて以下の形式で出力します。

ケース1の場合

1行目 You can go home in X steps.(半角英文字列)
2行目 1つ目の博士が取るべき行動(半角英文字列)
3行目 2つ目の博士が取るべき
.
.
X+1行目 X個目の博士が取るべき行動

ケース2の場合

1行目 You can not switch off all lights.(半角英文字列)

ケース3の場合

1行目 Help me!(半角英文字列)

Sample 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 for the Sample Input

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!

Source: PC Koshien 2007 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2007
http://www.pref.fukushima.jp/pc-concours/