#! /usr/bin/ruby

class Node
   #
   def initialize i, a
      @i = i      # index
      @a = [a]    # adjacents
      @c = nil    # colour
      @f = 0      # finished adjacents
      @l = nil
   end
   #
   attr_reader :i, :a
   attr_accessor :c, :f
   #
   def add a
      @a << a
   end
   #
   def to_s
      "#{@i} #{@c.to_s} " + @a.to_s
   end
   #
   def l
      return @l if not @l.nil?
      @l = @a.length
   end
   #
   def blocked?
      (l == @f)
   end
   #
end

class Step
   #
   def initialize n, c
      @n = n   # nodes
      @c = c   # max color
      @k = nil # current
      @f = []  # failed
      @p = n.select { |n| n.c.nil? } # possible
      # puts @p.inspect
      # @p[0].c = 666
      # puts @p[0].to_s
   end
   attr_reader :c, :n
   def done?
      @p.empty?
   end
   #
   def sort ar
      ar.sort { |a,b|
         r = b.l <=> a.l
         if r == 0
            b.f <=> a.f
         else
            r
         end
      }
   end
   #
   def chose_node
      b = @p.select { |n| n.blocked? }
      if not b.empty?
         return sort(b).shift
      end
      sort(@p).shift
   end
   #
   def test c
      @k.a.each do |i|
         if @n[i].c == c
            return false
         end
      end
      true
   end
   #
   def set_color c
      @k.c = c
      @k.a.each do |i|
         @n[i].f += 1
      end
   end
   #
   def try
      while not @p.empty?
         if @k.nil?
            @k = chose_node
            @p.delete @k
         end
         # puts "try #{@k.to_s}"
         co = nil
         cs = (@k.c.nil? ? 0 : @k.c )
         (cs..@c).each do |c|
            if test c
               co = c
               break
            end
         end
         if co.nil?
            @f << @k
            @k = nil
         else
            set_color co
            break
         end
      end
      # @n.each do |n| puts n.inspect end
      # puts @k.inspect
      # puts 'OK'
      true
   end
   #
   def next
      # TODO @k might be nil !!
      Step.new(@n.inject([]) {|a,n| a << n.clone}, ( (@k.c < @c) ? @c: @c+1))
   end
   #
end

class Graph
   #
   def initialize p, n, e
      @path = p
      @n = n
      @e = e
      @nodes = {}
      @edges = []
      @steps = []
      @c = 0
   end
   #
   def add e
      @edges << e

      a, b = *e
      a = a.to_i
      b = b.to_i

      n = @nodes[a]
      if n.nil?
         @nodes[a] = Node.new a, b
      else
         n.add b
      end

      n = @nodes[b.to_i]
      if n.nil?
         @nodes[b] = Node.new b, a
      else
         n.add a
      end
   end
   #
   def solve
      s = Step.new(@nodes.values.inject([]) {|a,n| a << n.clone}, @c)
      @steps << s
      while true
         if @steps.empty?
            puts 'unsolvable'
            return
         end
         if @steps[-1].try
            @steps << @steps[-1].next
            if @steps[-1].done?
               puts 'success'
               return
            end
         else
            @steps.pop
         end
      end
   end
   #
   def to_s
      r = "#{@p}: N:#{@n} E:#{@e}\n"
      @nodes.sort_by { |k,v| k } .each do |k,v|
         r += " #{v.to_s}\n"
      end
      r
   end
   #
   def draw
      puts "colors : #{@steps[-1].c}"
      require 'paleta'
      color = Paleta::Color.new(:hex, "0000ff")
      colors = Paleta::Palette.generate(:type => :complementary, :from => :color, :color => color, :size => @steps[-1].c).to_array(:rgb)
      df = @path+'.dot'
      pf = @path+'.png'
      open(df,'w') do |f|
         f << "graph {\n"
         f << "node [style=filled];\n"
         @steps[-1].n.each do |n|
            f << " #{n.i} [color=\"#{"#%02X%02X%02X" % colors[n.c]}\"]\n"
         end
         @edges.each do |a,b|
            f << " #{a} -- #{b}\n"
         end
         f << "}\n"
      end
      system "dot -Tpng -o '#{pf}' '#{df}'"
   end
   #
end

def read_graph path
   puts "read #{path}…"
   g = nil
   open(path).read.each_line do |line|
      if g.nil?
         g = Graph.new path, *line.split
         next
      end
      g.add line.split
   end
   puts "done."
   g
end

ARGV.each do |path|

   g = read_graph path
   g.solve
   puts g
   g.draw
end