//INSERIRE: COGNOME - NOME - NUMERO POSTAZIONE - PROFESSORE

//NON MODIFICARE il codice delle classi e dei metodi forniti
//NON AGGIUNGERE NUOVO CODICE al di fuori di quello richiesto

//PER COMPILARE USARE IL COMANDO:  "javac risultato.java"
//PER ESEGUIRE  USARE IL COMANDO:  "java Main"

import java.util.*;

class Graph  {
    
  private int[][] mat ;  
  private int[] mark;  
  private int nvert; 
  
  public Graph(int nv ) { 
    mat = new int[nv+1][nv+1];
    mark = new int[nv+1];
    nvert = nv;
    for (int i=1; i <= nvert; i++) 
       for (int j=1; j <= nvert; j++)
          mat[i][j] = 0;
  } 
  
  public void insArc( int i, int j ) {
     mat[i][j] = 1;
     return; 
  } 

  public IntStack path( int i, int j ) throws Exception {
    
    //Calcola, in modo ITERATIVO, 
    //un qualunque percorso (se esiste) da i a j
    
    IntStack st = new IntStack(nvert);
    for (int k=1; k <= nvert; k++) mark[k] = 0;
    st.push(i);
    mark[i] = 1;
    while( ! st.empty() && st.top() != j ) {
        int u = st.top();
        int v;  // se esiste un vertice adiacente non ancora visitato
        for ( v = 1; v <= nvert; v++ ) 
           if ( mat[u][v] == 1 && mark[v] != 1 ) {
              mark[v] = 1; st.push(v); break; //lo visita
           }
        if ( v > nvert ) { 
             System.out.println("Back da -> " + st.top());
             st.pop();  //non vi sono adiacenti non ancora visitati 
             }
    }
    return st;    
  } 
  
  public void print()  {
     System.out.println();
     System.out.print("Grafo:  " );
     for ( int i = 1; i <= nvert; i++ ) {
        System.out.println();
        for ( int j = 1; j <= nvert; j++ ) {
            System.out.print(mat[i][j] + "  ");
        }
     }
    return;
  }
  
}//class


class Main  {   
   public static void main( String argv[] ) throws Exception { 
    int nvert = 8;
    //GRAFO ORIENTATO
    Graph G = new Graph(nvert);
    G.insArc(1,2);
    G.insArc(1,2);
    G.insArc(2,4);
    G.insArc(2,5);
    G.insArc(3,2);
    G.insArc(4,1);
    G.insArc(4,2);
    G.insArc(4,6);
    G.insArc(6,7);
    G.insArc(7,4);
    G.insArc(7,5);
    G.insArc(8,3);
    G.insArc(4,8);
    G.print();
    System.out.println();
    
    IntStack st = G.path(1,3);
    while ( ! st.empty() ) {  
        System.out.println("--> " + st.pop());
    }    
    System.out.println();
  }
  
}//class