//============================================================================
// Name        : RootedTree.cpp
// Author      : Ken
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <vector>
#include <sstream>
using namespace std;

class Node{
public:
	int id;
	int height;
	Node* p_parent;
	Node* p_left_child;
	Node* p_right_child;

	Node(int n):id(n), p_parent(), p_left_child(), p_right_child(), height(-1){}
	Node(int n, Node& supernode):id(n), p_parent(&supernode), p_left_child(&supernode), p_right_child(&supernode), height(-1){}
};

void initializeNodes(vector<Node>& nodes, int n, Node& supernode){
	for(int i=0; i<n; i++){
		nodes.push_back(Node(i, supernode));
	}
}

string checkNodeType(vector<Node>& nodes, int i){
	if(i>=nodes.size()){
		cout << "ERROR!\n";
	}

	if(nodes.at(i).p_parent->id == -1){
		return "root";
	}

	if(nodes.at(i).p_left_child->id==-1 and nodes.at(i).p_right_child->id==-1){
		return "leaf";
	}

	return "internal node";
}

int checkDepth(vector<Node>& nodes, int i){
	if(i>=nodes.size()){
		cout << "ERROR!\n";
	}

	int depth = 0;
	Node* p_parent = nodes.at(i).p_parent;
	int id = p_parent->id;
	while(id != -1){
		depth ++;
		p_parent = p_parent->p_parent;
		id = p_parent->id;
	}

	return depth;
}

Node* getSibling(Node& node){
	if(node.id == node.p_parent->p_left_child->id){
		return node.p_parent->p_right_child;
	}else{ //if node.id == node.p_parent->p_right_child->id
		return node.p_parent->p_left_child;
	}
}

int getDegree(Node& node){
	int count = 0;
	if(node.p_left_child->id != -1){
		count ++;
	}

	if(node.p_right_child->id != -1){
		count ++;
	}

	return count;
}

void calcHeight(Node& node){
	if(node.p_left_child->id==-1 and node.p_right_child->id==-1){ // if the node is a leaf
		node.height = 0;
		return;
	}

	if(node.p_left_child->height==-1){
		calcHeight(*(node.p_left_child));
	}

	if(node.p_right_child->height==-1){
		calcHeight(*(node.p_right_child));
	}

	node.height = max(node.p_left_child->height, node.p_right_child->height) + 1;

}

void writePreorder(Node& node, stringstream& ss){
	ss << node.id << " ";
	if(node.p_left_child->id != -1){
	    writePreorder(*(node.p_left_child), ss);
	}

	if(node.p_right_child->id != -1){
	    writePreorder(*(node.p_right_child), ss);
	}
}

void writeInorder(Node& node, stringstream& ss){
	if(node.p_left_child->id != -1){
	    writeInorder(*(node.p_left_child), ss);
	}
	ss << node.id << " ";

	if(node.p_right_child->id != -1){
	    writeInorder(*(node.p_right_child), ss);
	}
}

void writePostorder(Node& node, stringstream& ss){
	if(node.p_left_child->id != -1){
	    writePostorder(*(node.p_left_child), ss);
	}

	if(node.p_right_child->id != -1){
	    writePostorder(*(node.p_right_child), ss);
	}
	ss << node.id << " ";
}

int findRoot(vector<Node>& nodes){
	int id = 0;

	for(int i=0; i<nodes.size(); i++){
		if(nodes.at(i).p_parent->id == -1){
			id = i;
		}
	}
	return id;
}


void writeTree(vector<Node>& nodes){
	//for(int i=0; i<nodes.size(); i++){
	//	cout << "node " << nodes.at(i).id << "\n";
	//}

	for(int i=0; i<nodes.size(); i++){

		cout << "node " << nodes.at(i).id << ": parent = " << nodes.at(i).p_parent->id;

		Node* p_sib = getSibling(nodes.at(i));
		cout << ", sibling = " << p_sib->id;

		int degree = getDegree(nodes.at(i));
		cout << ", degree = " << degree;

		int depth = checkDepth(nodes, i);
		cout << ", depth = " << depth;

		calcHeight(nodes.at(i));
		cout << ", height = " << nodes.at(i).height;

		string nodeType = checkNodeType(nodes, i);
		cout << ", " << nodeType << "\n";

		//cout << "in writeTree()\n";
	}
}



int main() {
	int n;
	cin >> n;
	vector<Node> nodes;
	Node SuperNode(-1);
	SuperNode.p_parent = &SuperNode;
	SuperNode.p_left_child = SuperNode.p_right_child = &SuperNode;

	//cout << "initializeNodes()\n";
	initializeNodes(nodes, n, SuperNode);

	//cout << "read nodes\n";
	for(int i=0; i<n; i++){
		//cout << "here: " << i << "\n";
		int id, l, r;
		cin >> id >> l >> r;

		if(l==-1){
			nodes.at(id).p_left_child = &SuperNode;
		}else{
		    nodes.at(id).p_left_child = &(nodes.at(l));
			nodes.at(l).p_parent = &(nodes.at(id));

		}

		if(r==-1){
			nodes.at(id).p_right_child = &SuperNode;
		}else{
			nodes.at(id).p_right_child = &(nodes.at(r));
			nodes.at(r).p_parent = &(nodes.at(id));
		}
	}

	//writeTree(nodes);
	int rootId = findRoot(nodes);

	stringstream ss1;
	cout << "Preorder\n";
	writePreorder(nodes.at(rootId), ss1);
	string str = ss1.str();
	cout << " " << str.substr(0, str.size()-1);
	cout << "\n";

	stringstream ss2;
	cout << "Inorder\n";
	writeInorder(nodes.at(rootId), ss2);
	str = ss2.str();
	cout << " " << str.substr(0, str.size()-1);
	cout << "\n";

	stringstream ss3;
	cout << "Postorder\n";
	writePostorder(nodes.at(rootId), ss3);
	str = ss3.str();
	cout << " " << str.substr(0, str.size()-1);
	cout << "\n";

	return 0;
}



Measured memory_bytes: 3200