#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <unordered_set>
//#include <gtest/gtest.h>
//#if defined(__unix__) || defined(__APPLE__)
//#include <sys/resource.h>
//#endif

using std::vector;
using std::ios_base;
using std::cin;
using std::cout;

class TreeOrders {
public:
	int n;
	vector<int> key;
	vector<int> left;
	vector<int> right;

	void read() {
		cin >> n;
		key.resize(n);
		left.resize(n);
		right.resize(n);
		for (int i = 0; i < n; i++) {
			cin >> key[i] >> left[i] >> right[i];
		}
	}

	vector<int> in_order() {
		std::stack<int> keyIndexStack;
		vector<int> result;
		bool walkLeft = true;
		int currentIndex = 0;
		keyIndexStack.push(currentIndex);
		while (!keyIndexStack.empty() || right[currentIndex] != -1) {
			if (walkLeft) {
				if (left[currentIndex] != -1) {
					currentIndex = left[currentIndex];
					keyIndexStack.push(currentIndex);
				} else {
					result.push_back(key[keyIndexStack.top()]);
					keyIndexStack.pop();
					walkLeft = false;
				}
			} else {
				if (right[currentIndex] != -1) {
					currentIndex = right[currentIndex];
					keyIndexStack.push(currentIndex);
					walkLeft = true;
				} else {
					if (!keyIndexStack.empty()) {
						currentIndex = keyIndexStack.top();
						keyIndexStack.pop();
						result.push_back(key[currentIndex]);
					}
				}
			}
		}
		return result;
	}

	vector<int> pre_order() {
		vector<int> result;
		std::stack<int> keyIndexStack;
		std::queue<int> keyIndexQueue;
		bool walkLeft = true;
		int currentIndex = 0;
		keyIndexStack.push(currentIndex);
		keyIndexQueue.push(currentIndex);
		while (!keyIndexStack.empty() || right[currentIndex] != -1) {
			if (walkLeft) {
				if (left[currentIndex] != -1) {
					currentIndex = left[currentIndex];
					keyIndexQueue.push(currentIndex);
					keyIndexStack.push(currentIndex);
				} else {
					keyIndexStack.pop();
					walkLeft = false;
					result.push_back(key[keyIndexQueue.front()]);
					keyIndexQueue.pop();
				}
			} else {
				if (right[currentIndex] != -1) {
					currentIndex = right[currentIndex];
					keyIndexQueue.push(currentIndex);
					keyIndexStack.push(currentIndex);
					walkLeft = true;
				} else {
					if (!keyIndexStack.empty()) {
						currentIndex = keyIndexStack.top();
						keyIndexStack.pop();
						result.push_back(key[keyIndexQueue.front()]);
						keyIndexQueue.pop();
					}
				}
			}
		}
		return result;
	}

	vector<int> post_order() {
		vector<int> result;
		std::stack<int> keyIndexStack;
		std::unordered_set<int> peekedSet;
		bool walkLeft = true;
		int currentIndex = 0;
		keyIndexStack.push(currentIndex);
		while (!keyIndexStack.empty()) {
			auto search = peekedSet.find(currentIndex);
			if (search != peekedSet.end()) {
				result.push_back(key[currentIndex]);
				peekedSet.erase(currentIndex);
				keyIndexStack.pop();
				if (keyIndexStack.empty())
					break;
				currentIndex = keyIndexStack.top();
				continue;
			}
			if (walkLeft) {
				if (left[currentIndex] != -1) {
					currentIndex = left[currentIndex];
					keyIndexStack.push(currentIndex);
				} else {
					if (right[currentIndex] == -1) {
						result.push_back(key[currentIndex]);
						walkLeft = false;
						keyIndexStack.pop();
						currentIndex = keyIndexStack.top();
					} else {
						peekedSet.insert(currentIndex);
						currentIndex = right[currentIndex];
						keyIndexStack.push(currentIndex);
					}
				}
			} else {
				if (right[currentIndex] != -1) {
					peekedSet.insert(currentIndex);
					currentIndex = right[currentIndex];
					keyIndexStack.push(currentIndex);
					walkLeft = true;
				} else {
					result.push_back(key[currentIndex]);
					int i = keyIndexStack.top();
					keyIndexStack.pop();
					if (i != currentIndex)
						result.push_back(key[i]);
					if (keyIndexStack.empty())
						break;
					currentIndex = keyIndexStack.top();
				}
			}
		}
		return result;
	}
};

void print(vector<int> a) {
	for (size_t i = 0; i < a.size(); i++) {
		if (i > 0) {
			cout << ' ';
		}
		cout << a[i];
	}
	cout << '\n';
}

//TEST(TreeTraversal, t) {
//	TreeOrders t;
//	t.key = {4, 2, 5, 1, 3};
//	t.left = {1, 3, -1, -1, -1};
//	t.right = {2, 4, -1, -1, -1};
//
//	vector<int> results = t.in_order();
//	ASSERT_EQ(5, results.size());
//	ASSERT_EQ(1, results[0]);
//	ASSERT_EQ(2, results[1]);
//	ASSERT_EQ(3, results[2]);
//	ASSERT_EQ(4, results[3]);
//	ASSERT_EQ(5, results[4]);
//
//	results = t.pre_order();
//	ASSERT_EQ(5, results.size());
//	ASSERT_EQ(4, results[0]);
//	ASSERT_EQ(2, results[1]);
//	ASSERT_EQ(1, results[2]);
//	ASSERT_EQ(3, results[3]);
//	ASSERT_EQ(5, results[4]);
//
//	results = t.post_order();
//	ASSERT_EQ(5, results.size());
//	ASSERT_EQ(1, results[0]);
//	ASSERT_EQ(3, results[1]);
//	ASSERT_EQ(2, results[2]);
//	ASSERT_EQ(5, results[3]);
//	ASSERT_EQ(4, results[4]);
//}

int main_with_large_stack_space() {
	ios_base::sync_with_stdio(0);
	TreeOrders t;
	t.read();
	print(t.in_order());
	print(t.pre_order());
	print(t.post_order());
	return 0;
}

int main (int argc, char **argv)
{
  return main_with_large_stack_space();
}