<?php
// solve1();
walk();

// 自力解
function solve1(){
	$n = (int)trim(fgets(STDIN));

	$list = [];
	for ($i=0; $i < $n; $i++) { 
		$node = new BTreeNode($i);
		$list[$node->getId()] = $node;
	}
	for ($i=0; $i < $n; $i++) { 
		$input = explode(' ', trim(fgets(STDIN)));
		$id = (int)$input[0];
		$list[$id]->setLeft((int)$input[1]);
		if (isset($list[(int)$input[1]])) {
			$list[(int)$input[1]]->setParentId($id);
		}
		$list[$id]->setRight((int)$input[2]);
		if (isset($list[(int)$input[2]])) {
			$list[(int)$input[2]]->setParentId($id);
		}
	}
	for ($i=0; $i < $n; $i++) { 
		if ($list[$i]->getParentId() === -1) {
			// root
			$curId = $i;
			break;
		}
	}
	// objectは参照渡しされるので、$listを参照渡しにしなくても$list内のobjectは関数内部で変更される！！
	dfs($list, $curId, 0);

	foreach ($list as $v) {
		$type = 'leaf';
		if ($v->getParentId() === -1) {
			$type = 'root';
		}elseif ($v->hasChild()) {
			$type = 'internal node';
		}
		$parent = $v->getParentId();
		$sibling = -1;
		if ($parent !== -1) {
			$sibling = $list[$parent]->getAnotherChild($v->getId());
		}
		echo 'node ' . $v->getId() .': parent = ' . $v->getParentId() .
			', sibling = ' . $sibling . ', degree = ' . count($v->getChildren()) . 
			', depth = ' . $v->getDepth() . ', height = ' . $v->getHeight() . ', ' . $type . PHP_EOL;
	}
}

function dfs($list, $id, $depth){
	$list[$id]->setDepth($depth);
	++$depth;
	$height = 0;
	if($list[$id]->hasChild()){
		$children = $list[$id]->getChildren();
		foreach ($children as $c) {
			$h = dfs($list, $c, $depth);
			$height = max($height, $h);
		}
	}
	$list[$id]->setHeight($height);
	return ++$height;
}

function walk(){
	$n = (int)trim(fgets(STDIN));

	$list = [];
	for ($i=0; $i < $n; $i++) { 
		$node = new BTreeNode($i);
		$list[$node->getId()] = $node;
	}
	for ($i=0; $i < $n; $i++) { 
		$input = explode(' ', trim(fgets(STDIN)));
		$id = (int)$input[0];
		$list[$id]->setLeft((int)$input[1]);
		if (isset($list[(int)$input[1]])) {
			$list[(int)$input[1]]->setParentId($id);
		}
		$list[$id]->setRight((int)$input[2]);
		if (isset($list[(int)$input[2]])) {
			$list[(int)$input[2]]->setParentId($id);
		}
	}
	for ($i=0; $i < $n; $i++) { 
		if ($list[$i]->getParentId() === -1) {
			// root
			$curId = $i;
			break;
		}
	}
	echo 'Preorder' . PHP_EOL;
	preorderWalk($list, $curId);
	echo PHP_EOL;

	echo 'Inorder' . PHP_EOL;
	inorderWalk($list, $curId);
	echo PHP_EOL;

	echo 'Postorder' . PHP_EOL;
	postorderWalk($list, $curId);
	echo PHP_EOL;

}


function preorderWalk($list, $id){
	echo ' ' . $id;
	if ($list[$id]->hasLeft()) {
		preorderWalk($list, $list[$id]->getLeft());
	}
	if ($list[$id]->hasRight()) {
		preorderWalk($list, $list[$id]->getRight());
	}
}

function inorderWalk($list, $id){
	if ($list[$id]->hasLeft()) {
		inorderWalk($list, $list[$id]->getLeft());
	}
	echo ' ' . $id;
	if ($list[$id]->hasRight()) {
		inorderWalk($list, $list[$id]->getRight());
	}
}
function postorderWalk($list, $id){
	if ($list[$id]->hasLeft()) {
		postorderWalk($list, $list[$id]->getLeft());
	}
	if ($list[$id]->hasRight()) {
		postorderWalk($list, $list[$id]->getRight());
	}
	echo ' ' . $id;
}

class BTreeNode
{
	private $id;
	private $depth = 0;
	private $height = 0;
	private $parent_id = -1;
	private $left = -1;
	private $right = -1;

	function __construct($id)
	{
		$this->id = $id;
	}
	function setParentId($p_id){
		$this->parent_id = $p_id;
	}
	function setLeft($l_id){
		$this->left = $l_id;
	}
	function setRight($r_id){
		$this->right = $r_id;
	}
	function getId(){
		return $this->id;
	}
	function getParentId(){
		return $this->parent_id;
	}
	function getLeft(){
		return $this->left;
	}
	function getRight(){
		return $this->right;
	}
	function hasChild(){
		return ($this->left !== -1) || ($this->right !== -1);
	}
	function getChildren(){
		$children = [];
		if ($this->hasLeft()) {
			$children[] = $this->left;
		}
		if ($this->hasRight()) {
			$children[] = $this->right;
		}
		return $children;
	}
	function getAnotherChild($c_id){
		$c = -1;
		if ($this->getLeft() === $c_id) {
			$c = $this->getRight();
		}elseif ($this->getRight() === $c_id) {
			$c = $this->getLeft();
		}
		return $c;
	}
	function hasLeft(){
		return $this->left !== -1;
	}
	function hasRight(){
		return $this->right !== -1;
	}
	function setDepth($d){
		$this->depth = $d;
	}
	function addDepth(){
		$this->depth += 1;
	}
	function getDepth(){
		return $this->depth;
	}
	function setHeight($h){
		$this->height = $h;
	}
	function getHeight(){
		return $this->height;
	}
}


Measured memory_bytes: 9412