// editor4

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

#define MAXN 105
#define MAXLEN 21

typedef struct {
    char name[MAXLEN];
    int left;   // index of left child in nodes array, -1 if NULL
    int right;  // index of right child in nodes array, -1 if NULL
} Node;

int main(void) {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0 || n > 100) {
        printf("Invalid input\n");
        return 0;
    }

    char parentNames[MAXN][MAXLEN];
    char leftNames[MAXN][MAXLEN];
    char rightNames[MAXN][MAXLEN];

    // Read all lines and basic validation (lengths, read success, duplicate parent names)
    for (int i = 0; i < n; ++i) {
        if (scanf("%20s %20s %20s", parentNames[i], leftNames[i], rightNames[i]) != 3) {
            printf("Invalid input\n");
            return 0;
        }
        int plen = (int)strlen(parentNames[i]);
        if (plen < 1 || plen > 20) { printf("Invalid input\n"); return 0; }
        if (strcmp(leftNames[i], "NULL") != 0) {
            int llen = (int)strlen(leftNames[i]);
            if (llen < 1 || llen > 20) { printf("Invalid input\n"); return 0; }
        }
        if (strcmp(rightNames[i], "NULL") != 0) {
            int rlen = (int)strlen(rightNames[i]);
            if (rlen < 1 || rlen > 20) { printf("Invalid input\n"); return 0; }
        }
        // check duplicate parent names so every parent is defined exactly once
        for (int j = 0; j < i; ++j) {
            if (strcmp(parentNames[j], parentNames[i]) == 0) {
                printf("Invalid input\n");
                return 0;
            }
        }
    }

    // Create nodes for each parent (index = 0..n-1)
    Node nodes[MAXN];
    for (int i = 0; i < n; ++i) {
        strncpy(nodes[i].name, parentNames[i], MAXLEN);
        nodes[i].name[MAXLEN-1] = '\0';
        nodes[i].left = nodes[i].right = -1;
    }

    // Helper: find parent index by name (linear search; n <= 100 so ok)
    auto findIndex = [&](const char *name) -> int {
        for (int i = 0; i < n; ++i) {
            if (strcmp(nodes[i].name, name) == 0) return i;
        }
        return -1;
    };

    // Link children, validate that child names are among defined parents
    int isChild[MAXN] = {0};
    for (int i = 0; i < n; ++i) {
        if (strcmp(leftNames[i], "NULL") != 0) {
            int li = findIndex(leftNames[i]);
            if (li == -1) { printf("Invalid input\n"); return 0; } // child not in parent list
            if (isChild[li]) { printf("Invalid input\n"); return 0; } // child already has a parent
            nodes[i].left = li;
            isChild[li] = 1;
        }
        if (strcmp(rightNames[i], "NULL") != 0) {
            int ri = findIndex(rightNames[i]);
            if (ri == -1) { printf("Invalid input\n"); return 0; } // child not in parent list
            if (isChild[ri]) { printf("Invalid input\n"); return 0; } // child already has a parent
            nodes[i].right = ri;
            isChild[ri] = 1;
        }
    }

    // There must be exactly one root (a node that is not anyone's child)
    int rootCount = 0, rootIdx = -1;
    for (int i = 0; i < n; ++i) {
        if (!isChild[i]) { rootCount++; rootIdx = i; }
    }
    if (rootCount != 1) { printf("Invalid input\n"); return 0; }

    // Preorder traversal with cycle detection and reachability check
    int visited[MAXN] = {0};
    int orderIdxs[MAXN];
    int outCnt = 0;
    int cycleDetected = 0;

    
    int stack[MAXN];
    int top = -1;
    stack[++top] = rootIdx;

    while (top >= 0) {
        int cur = stack[top--];
        if (visited[cur]) { cycleDetected = 1; break; } // revisited -> cycle
        visited[cur] = 1;
        orderIdxs[outCnt++] = cur;

        // push right then left so left is processed before right
        if (nodes[cur].right != -1) stack[++top] = nodes[cur].right;
        if (nodes[cur].left  != -1) stack[++top] = nodes[cur].left;
        if (top >= MAXN) { printf("Invalid input\n"); return 0; } // just in case
    }

    if (cycleDetected) { printf("Invalid input\n"); return 0; }

    // All defined parents must be reachable from root
    if (outCnt != n) { printf("Invalid input\n"); return 0; }

    // Print preorder names without trailing space
    if (outCnt > 0) {
        printf("%s", nodes[orderIdxs[0]].name);
        for (int i = 1; i < outCnt; ++i) {
            printf(" %s", nodes[orderIdxs[i]].name);
        }
    }
    printf("\n");
    return 0;
}