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=>[0,0]}
q=l[1]<1?[]:[l<<0]
(*t,a,c=q.shift
c+=1
(d[a].map{|i|t[i]>0&&[t.dup,i,"Move to room #{i}."]}+
r[a].map{|i|u=t.dup;v=u[i]^=1;a!=i &&[u,a,"Switch o#{v>0??n:"ff"} room #{i}."]})
.map{|v,i,s|v&&(!h[v<<i]||h[v][1]>c)&&(h[v]=[s,c,t+[a]];q<<(v+[c]))})while q[0]
puts (a=h[[0]*n+[1,n]])?(a,b,c=a
["You can go home in #{b} steps."]+(s=[a]
(a,b,c=h[c];s=[a]+s)while b>1
s)
):h.all?{|k,v|k[n+1]<n}?"Help me!":"You can not switch off all lights."
end