treasure.rb

class Chest
  attr_reader :type, :index, :keys
  def initialize(array, index)
    @type = array.shift.to_i
    @keys = array.shift(array.shift.to_i).map(&:to_i)
    @index = index
  end
  
  def unlock
    @keys
  end
end

class Array
  def without(x)
    self.reject { |e| e == x }
  end
end

def try(chest, rest, keys, path, results)
  (p path.size; return) if !keys.include?(chest.type) || !results.empty?

  (path << chest)
  (results << path) if rest.length == 0 
  (keys << chest.unlock); keys.flatten!; keys.delete_at(keys.index(chest.type))
  
  rest.select { |chest| keys.include? chest.type }.each do |chest|
    try(chest, rest.without(chest), keys.dup, path.dup, results)
  end
end


lines = IO.readlines('input.txt')
cases = lines.shift.to_i

index = 0
while lines.length > 0
  index = index + 1
  k, n = lines.shift.split.map(&:strip).map(&:to_i)
  keys = lines.shift.strip.split.map(&:to_i)
  chests = lines.shift(n).map(&:strip).map(&:split)
  chests.map!.with_index { |arr,i| Chest.new(arr, i + 1) }
  
  results = []

  puts "Case ##{index}: "  
  chests.each { |chest| try(chest, chests.without(chest), keys.dup, [], results)}


  if results.empty?
    puts "IMPOSSIBLE"
  else
    result = results.first.map(&:index)
    puts result.join(" ")
  end
end