import java.util.Scanner;
import java.io.File;

public class Graf 
{
    int n; // pocet vrcholov
    int m; // pocet hran
    
    Vrchol V[]; // mnozina vrcholov
    Hrana H[]; // mnozina hran
    
    public Graf( int n, int m ) 
    {
        this.n = n;
        this.m = m;
        
        this.V = new Vrchol[1+n];
        for ( int i = 1; i <= n; i++ )
        {
            this.V[i] = new Vrchol( i );
        }
        
        this.H = new Hrana[1+m];
    }
    
    public static Graf nacitajSubor( String nazovSuboru )
        throws java.io.FileNotFoundException
    {
        Scanner s = new Scanner( new File( nazovSuboru ) );
        int pocetVrcholov = s.nextInt();
        int pocetHran = s.nextInt();
        Graf g = new Graf( pocetVrcholov, pocetHran );
        for ( int i = 1; i <= pocetHran; i++ )
        {
            int u = s.nextInt();
            int v = s.nextInt();
            g.H[i] = new Hrana( g.V[u], g.V[v] );
        }
        
        return g;
    }
      
    private Hrana najdiHranu( Vrchol u )
    {
        for ( int j = 1; j <= m; j++ )
        {
            Hrana h = H[j];
            if ( h.u == u && !h.ptam && !h.hpp )
            {
                return h;
            }
            else if ( h.v == u && !h.pspat && !h.hpp )
            {
                return h;
            }
        }

        for ( int j = 1; j <= m; j++ )
        {
            Hrana h = H[j];
            if ( h.u == u && !h.ptam )
            {
                return h;
            }
            else if ( h.v == u && !h.pspat )
            {
                return h;
            }
        }
        
        return null;
    }
    
    public void tarry( int s )
    {
        // inicializacia
        
        // vsetky vrcholy su neobjavene
        for ( int i = 1; i <= n; i++ )
        {
            V[i].objaveny = false;
        }
        
        // vsetky su nepouzite
        for ( int j = 1; j <= m; j++ )
        {
            H[j].hpp = false;
            H[j].ptam = false;
            H[j].pspat = false;
        }

        // posledny vrchol v tarryho slede
        Vrchol u = V[s];
        u.objaveny = true;

        System.out.println( 
            "Tarryho sled so zaciatkom vo vrchole " 
            + s + ":" );
        
        Hrana h;
        while ( (h = najdiHranu( u )) != null )
        {
            Vrchol v;
            if ( h.u == u )
            {
                // idem hranu pouzit v smere tam
                v = h.v;
                h.ptam = true;
            }
            else
            {
                // idem hranu pouzit v smere spat
                v = h.u;
                h.pspat = true;
            }
            
            System.out.println(
                "Pouzil som hranu {" + u.cislo
                    + "," + v.cislo + "}." );
                    
            if ( !v.objaveny )
            {
                System.out.println( 
                    "Objavil som vrchol " + v.cislo + "." );
                    
                v.objaveny = true;
                h.hpp = true;
            }
            
            u = v;
        }
        
        // idem zistit, ci je graf suvisly
        // na zaciatku prdpokladam, ze je suvisly
        boolean jeSuvisly = true;
        
        // prejdem vsetky vrcholy
        for ( int i = 1; i <= n; i++ )
        {
            if ( !V[i].objaveny )
            {
                // mam neobjaveny vrchol, graf NIE je suvisly
                jeSuvisly = false;
                // je zbytocne prechadzat ostatne vrcholy
                break;
            }
        }
        
        if ( jeSuvisly )
        {
            System.out.println( "Zadany graf JE suvisly." );
        }
        else
        {
            System.out.println( "Zadany graf NIE JE suvisly." );
            
            // vypisem zoznam objavenych vrcholov
            System.out.print( "Objavene vrcholy grafu:" );
            for ( int i = 1; i <= n; i++ )
            {
                if ( V[i].objaveny )
                    System.out.print( " " + V[i].cislo );
            }
            System.out.println();
            
            // vypisem zoznam neobjavenych vrcholov
            System.out.print( "Neobjavene vrcholy grafu:" );
            for ( int i = 1; i <= n; i++ )
            {
                if ( !V[i].objaveny )
                    System.out.print( " " + V[i].cislo );
            }
            System.out.println();
        }
    }
}