#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 101

// Structure for tree node
typedef struct Node {
    char task[25];
    struct Node *left, *right;
} Node;

// Create a new node
Node* createNode(char *task) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    strcpy(newNode->task, task);
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Search node in tree
Node* search(Node* root, char* task) {
    if (root == NULL) return NULL;
    if (strcmp(root->task, task) == 0) return root;
    Node* left = search(root->left, task);
    if (left) return left;
    return search(root->right, task);
}

// Preorder traversal
void preorder(Node* root) {
    if (root == NULL) return;
    printf("%s ", root->task);
    preorder(root->left);
    preorder(root->right);
}

int main() {
    int n;
    scanf("%d", &n);

    if (n <= 0 || n > 100) {
        printf("Invalid input");
        return 0;
    }

    Node* root = NULL;
    for (int i = 0; i < n; i++) {
        char task[25], left[25], right[25];
        scanf("%s %s %s", task, left, right);

        // If tree empty, create root
        if (root == NULL) {
            root = createNode(task);
            if (strcmp(left, "NULL") != 0)
                root->left = createNode(left);
            if (strcmp(right, "NULL") != 0)
                root->right = createNode(right);
        } else {
            Node* parent = search(root, task);
            if (parent == NULL) continue;
            if (strcmp(left, "NULL") != 0 && parent->left == NULL)
                parent->left = createNode(left);
            if (strcmp(right, "NULL") != 0 && parent->right == NULL)
                parent->right = createNode(right);
        }
    }

    preorder(root);
    return 0;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 101

// Structure for tree node
typedef struct Node {
    char task[25];
    struct Node *left, *right;
} Node;

// Create a new node
Node* createNode(char *task) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    strcpy(newNode->task, task);
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Search node in tree
Node* search(Node* root, char* task) {
    if (root == NULL) return NULL;
    if (strcmp(root->task, task) == 0) return root;
    Node* left = search(root->left, task);
    if (left) return left;
    return search(root->right, task);
}

// Preorder traversal
void preorder(Node* root) {
    if (root == NULL) return;
    printf("%s ", root->task);
    preorder(root->left);
    preorder(root->right);
}

int main() {
    int n;
    scanf("%d", &n);

    if (n <= 0 || n > 100) {
        printf("Invalid input");
        return 0;
    }

    Node* root = NULL;
    for (int i = 0; i < n; i++) {
        char task[25], left[25], right[25];
        scanf("%s %s %s", task, left, right);

        // If tree empty, create root
        if (root == NULL) {
            root = createNode(task);
            if (strcmp(left, "NULL") != 0)
                root->left = createNode(left);
            if (strcmp(right, "NULL") != 0)
                root->right = createNode(right);
        } else {
            Node* parent = search(root, task);
            if (parent == NULL) continue;
            if (strcmp(left, "NULL") != 0 && parent->left == NULL)
                parent->left = createNode(left);
            if (strcmp(right, "NULL") != 0 && parent->right == NULL)
                parent->right = createNode(right);
        }
    }

    preorder(root);
    return 0;
}