1require 'set'
  2
  3class SocialGraph
  4  attr_reader :reader, :writer
  5
  6  def initialize(reader, writer)
  7    @reader, @writer = reader, writer
  8    @members = Hash.new { |hash, key| hash[key] = Member.new(key) }
  9  end
 10
 11  def run(traversal = Traversal.new(writer))
 12    (reader.readline.to_i - 1).times do
 13      add_to_graph(reader.readline.strip)
 14    end
 15
 16    member_for(reader.readline).tap do |root|
 17      traversal.traverse(root)
 18    end
 19  end
 20
 21  private
 22
 23  def add_to_graph(line)
 24    key, friend_keys = line.split(':')
 25    friend_keys.split(',').each do |friend|
 26      member_for(key).add_friend(member_for(friend))
 27    end unless friend_keys.nil?
 28  end
 29
 30  def member_for(key)
 31    @members[key.strip]
 32  end
 33end
 34
 35class Member
 36  include Enumerable
 37
 38  attr_reader :name
 39
 40  def initialize(name)
 41    @name = name
 42    @friends = []
 43  end
 44
 45  def add_friend(friend)
 46    @friends << friend
 47  end
 48
 49  def each
 50    @friends.each do |friend|
 51      yield friend
 52    end
 53  end
 54
 55  def to_s
 56    name
 57  end
 58
 59  def inspect
 60    name
 61  end
 62
 63  def ==(other)
 64    name == other.name
 65  end
 66end
 67
 68class Traversal
 69  attr_reader :writer
 70
 71  def initialize(writer)
 72    @writer = writer
 73    @visited = { }
 74    @queue = []
 75  end
 76
 77  def traverse(member)
 78    @queue = []
 79    @root = member
 80    @queue.push(member)
 81    until @queue.empty? do
 82      member = @queue.shift
 83      write(newline) if member.nil? && @queue.first
 84      next if member.nil?
 85
 86      visit(member)
 87      added = false
 88      member.each do |friend|
 89        @queue.push(friend) if eligible?(friend)
 90        added = true
 91      end
 92
 93      @queue.push(nil) if added
 94    end
 95  end
 96
 97  private
 98
 99  def eligible?(member)
100    !visited?(member) && !root?(member) && !queued?(member)
101  end
102
103  def newline
104    "\n"
105  end
106
107  def queued?(friend)
108    @queue.find { |x| x == friend }
109  end
110
111  def visit(member)
112    return if visited?(member) || root?(member)
113    write(member.name) unless root?(member)
114    write(",") unless @queue.first.nil?
115    @visited[member.name] = true
116  end
117
118  def visited?(member)
119    @visited.key?(member.name)
120  end
121
122  def root?(member)
123    @root.name == member.name
124  end
125
126  def write(value)
127    writer.write(value)
128  end
129end