#include <iostream>
#include <conio.h>
#include <iomanip>
#include <stdio.h>

using namespace std;

const int maxx = 100;

int cities;
int road;
int TOUR[maxx];
int Available[maxx];


 
bool VALID_ROAD[maxx][maxx];
bool VALID_CITY[maxx];

int current_city, moving_city;

/*Khoi tao so dò giao thong */
void INITIAL()
{
        for ( int i = 0; i < cities; i++ )
                for ( int j = 0; j < cities; j++ )
                        VALID_ROAD[i][j] = false;
                
        for ( int i = 0; i < cities; i++ )
                VALID_CITY[i] = true;
        
}


void PRINT( int Z )
{
        for ( int i = 0; i < Z ; i++ )
        {
                cout << TOUR[i] << " -> " ;
        }
        cout << "\n\n";
}

void JOURNEY ( int i )
{
        for ( int j = 2; j <= cities; j++ )
        {
                if ( VALID_CITY[i] == true && VALID_ROAD[i][j] == true )
                {
                        TOUR[i] = j;
                        if ( TOUR[i] == moving_city ) /*Khi da toi dc TP càn tói, in ra ket qua hành trình */
                        {
                                PRINT(i+1); getch();
                        }
                        /*Neu chua toi goi de qui di tiep */
                        else
                        {
                                VALID_ROAD[i][j] = false;
                                VALID_CITY[i] = false;
                                JOURNEY ( i + 1 );
                                VALID_CITY[i] = true;
                                VALID_ROAD[i][j] = true;
                        }
                }
        }
}

int main()
{
       
        int first_city, second_city;
       
    
        cout << "Enter the number of city: ";        cin >> cities;
        cout << "Enter the number of valid-road: ";  cin >> road;
        
        INITIAL();
        
        cout << "---------------ENDL-------------" << endl;
        cout << "Now, what city are you living in : ";      cin >> current_city;  
        cout << "What city would you like to move to :  -> ";  cin >> moving_city; 
        
       
        cout << "-----------INFORMATION MAP-------------" << endl;
        cout << "-----*-----[-------------]-----*-------" << endl;
        cout << "-----*------[-----------]------*-------" << endl;
        cout << "-----*-------[---------]-------*-------" << endl;
        cout << "-----*--------[-------]--------*-------" << endl;
        cout << "-----*---------[-----]---------*-------" << endl;
        cout << "\n\n";
        
       

        /*Nhâp thong tin cho nhung duogn có hieu luc, TP nào có the tói TP nào */
        int times = 0;
        do
        {
                cout << " THE " << times + 1 << "  ROAD" << endl;
                cout << "First city : [";  cin  >> first_city;  cout << " --->>> ";
                cout << "Second city: [";  cin  >> second_city;
                
                
                cout << "-----|-|-|-|-|-|-|-|-----" << endl;    
                
                VALID_ROAD[first_city][second_city] = true;
                VALID_ROAD[second_city][first_city] = true;
                
                times++;
                Available[times] = second_city;
                
        } while ( times < road );

     
        /* Kiem tra xem có duong di toi TP càn toi không ? */
        int check_times = 0;
        for ( int i = 0; i <= road; i++ )
        {
                if ( Available[i] == moving_city ) check_times++; 
        }
       
                        if ( check_times == 0 )
                        {
                                cout << "No way for you to move: ";
                        }
                        else
                        {
                                 TOUR[0] = current_city;
                                 JOURNEY ( current_city );
                        }
        getch();
        return 0;
}