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

typedef struct _treenode {
   int id;
   struct _treenode *L;
   struct _treenode *R;
} treenode;

typedef treenode *tree;

int nlp = 0;

tree readtree ( )
{
   int n, i, id, L, R;
   treenode *nodearray;
   int *isroot;

   scanf("%d", &n);
   /* It does not matter whether we allocate n nodes one by one,
      or in a single chunk, so I go for the second alternative. */
   nodearray = (tree)malloc(n * sizeof(treenode));
   isroot = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) {
       nodearray[i].id = i;
       nodearray[i].L = NULL;
       nodearray[i].R = NULL;
       isroot[i] = 1;
   }
   for (i=0; i<n; ++i) {
      scanf("%d%d%d", &id, &L, &R);
      if (L >= 0) { nodearray[i].L = &(nodearray[L]); isroot[L] = 0; }
      if (R >= 0) { nodearray[i].R = &(nodearray[R]); isroot[R] = 0; }
   }
   for (i=0; i<n; ++i) if (isroot[i]) return &(nodearray[i]);
   return NULL;
}

void printleaves ( tree T )
{
   if (T == NULL) return;
   printleaves(T -> L);
   if ((T -> L == NULL) && (T -> R == NULL)) {
      printf("%4d", T -> id);
      if (++nlp == 18) { printf("\n    "); nlp = 0; }
   }
   printleaves(T -> R);
}

int maxleaflevel ( tree T, int level )
{
   int l, r;

   if (T == NULL) return -1;
   if ((T -> L == NULL) && (T -> R == NULL)) return level;
   l = maxleaflevel(T -> L, level + 1);
   r = maxleaflevel(T -> R, level + 1);
   return (l >= r) ? l : r;
}

int minleaflevel ( tree T, int level )
{
   int l, r;

   if (T == NULL) return 1000000000;
   if ((T -> L == NULL) && (T -> R == NULL)) return level;
   l = minleaflevel(T -> L, level + 1);
   r = minleaflevel(T -> R, level + 1);
   return (l <= r) ? l : r;
}

void leavesatlevel ( tree T, int level, int LEVEL )
{
   if (T == NULL) return;
   if ((T -> L == NULL) && (T -> R == NULL)) {
      if (level == LEVEL) printf("%d ", T -> id);
      return;
   }
   if (T -> L != NULL) leavesatlevel(T->L,level+1,LEVEL);
   if (T -> R != NULL) leavesatlevel(T->R,level+1,LEVEL);
}

void printpaths ( tree T, int level, int ID[], int LEVEL )
{
   int i;

   if (T == NULL) return;
   if ((T -> L == NULL) && (T -> R == NULL)) {
      if (level == LEVEL) {
         printf("\t");
         for (i=0; i<level; ++i) printf("%d-", ID[i]);
         printf("%d\n", ID[level]);
      }
      return;
   }
   if (T -> L != NULL) {
      ID[level + 1] = T -> L -> id;
      printpaths(T -> L, level + 1, ID, LEVEL);
   }
   if (T -> R != NULL) {
      ID[level + 1] = T -> R -> id;
      printpaths(T -> R, level + 1, ID, LEVEL);
   }
}

int main ( )
{
   tree T;
   int l, s, ID[1000];

   T = readtree();
   printf("Id of root = %d\n", T -> id);
   printf("Leaves in the tree are\n    ");
   printleaves(T);
   printf("\n");
   l = maxleaflevel(T,0); s = minleaflevel(T,0);
   printf("Maximum level of a leaf in T is %d\n", l);
   printf("Minimum level of a leaf in T is %d\n", s);
   printf("Leaves at maximum level are "); leavesatlevel(T,0,l); printf("\n");
   printf("Leaves at minimum level are "); leavesatlevel(T,0,s); printf("\n");
   printf("Longest root-to-leaf paths:\n"); ID[0] = T -> id; printpaths(T,0,ID,l);
   printf("Shortest root-to-leaf paths:\n"); ID[0] = T -> id; printpaths(T,0,ID,s);
   exit(0);
}