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

typedef struct cvor
{
    struct cvor *l, *d;
    int br;
} cvor;

cvor *novi( int x )
{
    cvor *koren = ( cvor * ) malloc( sizeof( cvor ) );
    koren -> l = koren -> d = NULL;
    koren -> br = x;

    return koren;
}

cvor *nadji( cvor *koren, int x )
{
    if( !koren ) return NULL;

    if( koren -> br == x ) return koren;

    cvor *pom = nadji( koren -> l, x );

    if( pom ) return pom;

    return nadji( koren -> d, x );
}

cvor *kreirajStablo()
{
    int x;
    scanf("%d", &x );
    cvor *koren = novi( x );

    int r;
    scanf("%d", &r );
    while( r )
    {
        int levi, desni;
        scanf("%d%d", &levi, &desni );
        
        cvor *pom = nadji( koren, r );

        if( levi ) pom -> l = novi( levi );
        if( desni ) pom -> d = novi( desni );

        scanf("%d", &r );
    }

    return koren;
}

void razmak( int n )
{
    for( int i = 0; i < n; i ++ ) putchar('\t');
}

void vizuelniPrikaz( cvor *koren, int nivo )
{
    if( !koren )
    {
        razmak( nivo );
        puts("~");
    }
    else
    {
        vizuelniPrikaz( koren -> d, nivo + 1 );
        razmak( nivo );
        printf("%d\n", koren -> br );
        vizuelniPrikaz( koren -> l, nivo + 1 );
    }
}

int nzp_( cvor *koren, cvor *x, cvor *y, cvor **resenje )
{
    if( !koren ) return 0;

    if( koren == x || koren == y )
    {
        *resenje = koren;
        return 1;
    }

    int levo = nzp_( koren -> l, x, y, resenje );
    int desno = nzp_( koren -> d, x, y, resenje );

    if( levo && desno ) *resenje = koren;

    return levo || desno;
}

int nzp( cvor *koren, int x, int y )
{
    cvor *resenje;
    nzp_( koren, nadji( koren, x ), nadji( koren, y ), &resenje );

    return resenje -> br;
}

void orezivanje( cvor *koren, int lb, int ub )
{
    if( koren -> l )
        if( koren -> l -> br < koren -> br 
         && koren -> l -> br >= lb ) orezivanje( koren -> l, lb, koren -> br );
        else koren -> l = NULL;

    if( koren -> d )
        if( koren -> d -> br >= koren -> br 
         && koren -> d -> br < ub ) orezivanje( koren -> d, koren -> br, ub );
        else koren -> d = NULL;
}

int main()
{
    cvor *koren = kreirajStablo();
    vizuelniPrikaz( koren, 0 );

    orezivanje( koren, -INT_MAX, INT_MAX );

    vizuelniPrikaz( koren, 0 );

    // int m;
    // scanf("%d", &m );

    // while( m -- )
    // {
    //     int x, y;
    //     scanf("%d%d", &x, &y );

    //     printf("%d\n", nzp( koren, x , y ) );
    // }



    return 0;
}