def g;gets.split.map &:to_i;end
while(n,m=g)[0]>0
d=(0..n).map{[]}
m.times{s,t=g;d[s]<<t;d[t]<<s}
l=[0]+g
r=[0]+(1..n).map{g[1..-1].sort}
h={l<<1=>[]}
q=l[1]<1?[]:[l]
q.map{|w|*t,a=w
d[a].map{|i|t[i]>0&&h[v=t+[i]]||=(q<<v;["Move to room #{i}.",w])}
r[a].map{|i|u=w.dup;v=u[i]^=1;a!=i &&h[u]||=(q<<u;["Switch o#{v>0??n:"ff"} room #{i}.",w])}}
puts (h[c=[0]*n+[1,n]])?(s=[]
s=[l]+s while(l,c=h[c])[1]
["You can go home in #{s.size} steps."]+s):h.all?{|k,v|k[n+1]<n}?"Help me!":"You can not switch off all lights."
end