#!/usr/local/bin/ruby
#-*- coding: Windows-31J -*-

module Dunber
  M = 2     # 点はM次以下の隔たりで繋がっていなければならない
  N = 3     # 点から出る辺の数は最大N本
  NUM = 10  # ノードの数NUMの場合の解を求める
  
  class Node
    attr_reader :id, :edges
    attr_accessor :dist
    
    def initialize(id)
      @id = id
      @edges = [@id]
      @dist = 0
    end
    
    def add(x)
      @edges.push(x)
    end
    
    def addable?(x)
      if full?
        return false
      else
        not @edges.include?(x)
      end
    end
    
    def full?
      @edges.size >= N + 1
    end
    
    def to_s
      "#{@edges}"
    end
  end
  
  class Tree
    attr_reader :nodes
    
    def initialize
      @nodes = []
      (0...NUM).each do |i|
        @nodes.push Node.new(i)
      end
    end

    def shuffle
      @nodes.each do |node|
        arr = (node.id...NUM).to_a
        next if arr.size == 0
        
        arr = arr.select do |i|
          @nodes[i].addable?(node.id)
        end
        arr = arr.sort_by{|a| rand}
        
        (N+1 - node.edges.size).times do
          add(node.id, arr.pop) if arr.size > 0
        end
      end
    end
    
    def add(a, b)
      @nodes[a].add(b)
      @nodes[b].add(a)
    end
    
    def valid?
      @nodes.each do |node|
        return false unless valid_sub?(node)
      end
      return true
    end
    
    def valid_sub?(node)
      clear_dists
      paint(node, M+1)
      valid_dist?(node.id)
    end
    
    def paint(node, m)
      if node.dist < m
        node.dist = m
        node.edges.each do |edge|
          paint(@nodes[edge], m-1)
        end
      end
    end
    
    def clear_dists
      @nodes.each do |node|
        node.dist = 0
      end
    end
    
    def valid_dist?(start)
      @nodes.each do |node|
        if node.dist == 0
          puts "#{start}と#{node.id}がつながりません。"
          return false
        end
      end
      return true
    end
    
    def to_s
      str = "#{@nodes.size}個のノード。\n"
      str += "#{count_edges}本のエッジ。\n"
      @nodes.each do |node|
        str += "#{node.to_s}\n"
      end
      str
    end

    def count_edges
      count = 0
      @nodes.each do |node|
        count += node.edges.size
      end
      count = (count - @nodes.size) / 2
    end
    
  end
  
  def self.main
    loop do
      tree = Tree.new
      tree.shuffle
      if tree.valid?
        puts "解を発見しました！"
        puts tree
        break
      end
    end
  end
  
end

Dunber.main