//  INSERIRE: COGNOME  NOME  PROFESSORE  POSTAZIONE



class ArrayBinTreeBFS {

    

    //"tree" e' la rappresentazione lineare dell'albero binario

    //"n" e' il numero di nodi (interni) dell'albero binario

    

    int n;

    boolean mark[];

    int tree[];

    

    ArrayBinTreeBFS ( int num_nodi ) {

       n = num_nodi;

       mark = new boolean[n+1];

       tree = new int[n+1];  

       for (int i=1; i <= n; i++) mark[i] = false;

       for (int i=1; i <= n; i++) tree[i] = i;

    }

    

    boolean isInternal( int i ) { return i <= n; }

    

    boolean isExternal( int i ) { return i > n; }

    

    int leftChild( int i ) { return 2*i; }

    

    int rightChild( int i ) { return 2*i + 1; }

    

    int parent( int i ) { return i/2; }

    

    void unMarkAll() { 

        for (int i=1; i <= n; i++) mark[i] = false;    

    }

    void mark( int i ) { mark[i]=true; } 

    boolean isMarked( int i ) { return mark[i]; } 



    public int[] pathBFS( int s, int z ) throws Exception {

        

       int pred[] = new int[n+1];

       

       //INSERIRE QUI' IL CODICE SOLUZIONE DEL PROBLEMA

       

       return pred;

    }

           

    void printBFSPath( int pred[], int z ) {

       //stampa il percorso al rovescio 

       System.out.print("\nPercorso: ");

       int x = z;

       while ( pred[x] != 0 ) {

          System.out.print("  " + x );

          x = pred[x];

       } 

       System.out.print("  " + x );

    }

} 



class Main {   

  public static void main( String argv[] ) throws Exception {

    int n = 15; //numero nodi interni

    int s = 13; //nodo origine

    int z = 5;  //nodo destinazione

    ArrayBinTreeBFS tree = new ArrayBinTreeBFS(n);

    tree.printBFSPath(tree.pathBFS(s,z),z);    

    System.out.println();

  }

}