public class Kreistest extends Graph
{
    private static int[] alpha, sohn;

    private static void KreisAusgeben(int w,int v)
    {
        System.out.println("Der Graph enthaelt mindestens einen Kreis, z.B.");

        // wir wissen, dass (v,w) eine B-Kante ist.  Von w beginnend
        // koennen wir nun einen Kreis ausgeben, indem wir solange
        // die in Bearbeitung befindlichen Nachfolger von w ausgeben
        // bis wir auf v stossen.  Die Nachfolger finden wir, indem
        // wir den Verweisen im Array sohn folgen.
        while (w != v) 
        {     
              System.out.print((w+1)+" ");
              w = sohn[w]; 
        }
        System.out.println(v+1);
    }

    private static boolean KreisFinden(int v)
    { 
        // aktuellen Knoten als "in Bearbeitung" markieren
        alpha[v] = 1;

        // Adjazenzliste durchsuchen
        for (Node t = adjazenz[v]; t!=null; t = t.successor())
        {
           int w = t.readnumber()-1;
           if (alpha[w]==0) 
           { 
	       // w ist ein bisher unbesuchter Knoten;
               // wir merken uns zunaechst im Array sohn, dass wir ihn
               // von v aus besuchen wollen ....
               sohn[v]=w;
               // ... und tun dies dann auch.  Falls wir dabei einen Kreis
               // finden sind wir fertig
               if (KreisFinden(w)) return true;
           }
           else if (alpha[w]==1) 
           { 
               // Wir haben eine B-Kante gefunden und damit einen Kreis.
               // Diesen geben wir aus und sind damit fertig
               KreisAusgeben(w,v); return true;
           }
        }
        // aktuellen Knoten als "vollstaendig bearbeitet" markieren
        alpha[v]=2;

        // Da wir die Methode nicht vorher verlassen haben, haben wir bisher
        // keinen Kreis gefunden
        return false;
    }

    public static void Kreis()
    {
        alpha = new int[vnumber];
        sohn  = new int[vnumber];
 
        // alpha initialisieren
        for (int x=0; x<vnumber; x++) alpha[x]=0;
    
        int x;
        // die Tiefensuche fuer bisher unbesuchte Knoten anstossen
        // bis wir einen Kreis finden
        for (x=0; x<vnumber; x++)
             if (alpha[x]==0) 
                  if (KreisFinden(x)) break;
        
        // Wenn wir die for-Schleife nicht vorzeitig verlassen haben,
        // wurde kein Kreis gefunden
        if (x==vnumber) 
             System.out.println("Der Graph ist kreisfrei");
    }

    public static void main(String args[])
    {
	read();
        print();
        Kreis();
    }
}