class Node
  attr_reader :id, :left, :right
  attr_accessor :parent
  protected :parent=

  def initialize(id)
    @id = id
  end

  def left=(node)
    @left = node
    node.parent = self
  end

  def right=(node)
    @right = node
    node.parent = self
  end

  def grand_parent
    @parent.nil? ? self : @parent.grand_parent
  end
end

class NodeRepository
  include Enumerable

  def initialize
    @store = {}
  end

  def [](id)
    @store[id] ||= Node.new(id)
  end

  # The order may be random.
  def each(&block)
    Enumerator.new do |y|
      @store.each { |_, v| y << v }
    end.each(&block)
  end
end
repo = NodeRepository.new

n = gets.chomp.to_i
n.times do
  current, left, right = gets.chomp.split(' ').map(&:to_i)
  node = repo[current]
  node.left = repo[left] if left != -1
  node.right = repo[right] if right != -1
end
root = repo.first.grand_parent

class TreeWalker
  def self.enum_node_preorder(node, &block)
    yield node
    enum_node_preorder(node.left, &block) if node.left
    enum_node_preorder(node.right, &block) if node.right
  end
  def self.enum_node_inorder(node, &block)
    enum_node_inorder(node.left, &block) if node.left
    yield node
    enum_node_inorder(node.right, &block) if node.right
  end
  def self.enum_node_postorder(node, &block)
    enum_node_postorder(node.left, &block) if node.left
    enum_node_postorder(node.right, &block) if node.right
    yield node
  end

  def initialize(root)
    @root = root
  end

  def enum_preorder(&block)
    self.class.enum_node_preorder(@root, &block)
  end
  def enum_inorder(&block)
    self.class.enum_node_inorder(@root, &block)
  end
  def enum_postorder(&block)
    self.class.enum_node_postorder(@root, &block)
  end
end
walker = TreeWalker.new(root)

puts "Preorder"
print ' '
puts walker.to_enum(:enum_preorder).map(&:id).join(' ')

puts "Inorder"
print ' '
puts walker.to_enum(:enum_inorder).map(&:id).join(' ')

puts "Postorder"
print ' '
puts walker.to_enum(:enum_postorder).map(&:id).join(' ')

