# Node
class Node
  attr_accessor :id, :parent, :left, :right

  def initialize(id, parent = nil, left = nil, right = nil)
    @id, @parent, @left, @right = id, parent, left, right
  end
end

# BinaryTree
class BinaryTree
  attr_accessor :nodes

  def initialize(data)
    @nodes = data.each_with_object({}) do |(key, value), hash|
      hash[key] = Node.new(key, value[:parent], value[:left], value[:right])
    end
  end

  def depth(id)
    node = @nodes[id]
    unless node.parent.nil?
      return depth(node.parent) + 1
    else
      return 0
    end
  end

  def root?(id)
    node = @nodes[id]
    node.parent.nil?
  end

  def leaf?(id)
    children(id).empty?
  end

  def sibling(id)
    parent = @nodes[id].parent
    unless parent.nil?
      s = children(parent).select { |child| id != child }
      return s.any? ? s.shift : -1
    end
    -1
  end

  def degree(id)
    children(id).length
  end

  def height(id)
    c = children(id)
    unless c.empty?
      heights = []
      c.each do |child|
        heights << height(child) + 1
      end
      return heights.max
    else
      return 0
    end
  end

  def root
    @nodes.values.find { |node| root?(node.id) }
  end

  def preorder(id)
    stack, list = [id], []

    until stack.empty?
      node = @nodes[stack.pop]
      list << node
      stack << node.right unless node.right == -1
      stack << node.left unless node.left == -1
    end

    list
  end

  def inorder(id)
    stack, list = [], []

    until stack.empty? && id == -1
      if id != -1
        stack << id
        id = @nodes[id].left
      else
        node = @nodes[stack.pop]
        list << node
        id = node.right
      end
    end

    list
  end

  def postorder(id)
    stack, list = [], []
    last = -1

    until stack.empty? && id == -1
      if id != -1
        stack << id
        id = @nodes[id].left
      else
        peek_node = @nodes[stack.last]
        if peek_node.right != -1 && last != peek_node.right
          id = peek_node.right
        else
          list << peek_node
          last = @nodes[stack.pop].id
        end
      end
    end

    list
  end

  private

  def children(id)
    node = @nodes[id]
    [node.left, node.right].select { |i| i != -1 }
  end
end

data = {}
parent = {}

n = gets.chop.to_i

n.times do
  id, left, right = gets.chop.split.map(&:to_i)
  data[id] = { :left => left, :right => right }
  parent[left] = parent[right] = id
end

data.each do |key, value|
  value[:parent] = parent[key]
end

data = Hash[data.sort]

t = BinaryTree.new(data)
root = t.root

puts 'Preorder'
out = []
t.preorder(root.id).each do |node|
  out << node.id
end
puts " #{out.join(' ')}"
puts 'Inorder'
out = []
t.inorder(root.id).each do |node|
  out << node.id
end
puts " #{out.join(' ')}"
puts 'Postorder'
out = []
t.postorder(root.id).each do |node|
  out << node.id
end
puts " #{out.join(' ')}"