#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

// individual connection data class
class RoomConnection {
  public:
    int roomin;
    int roomout;
    
    RoomConnection() {}
    RoomConnection(int n1, int n2) {
        roomin  = n1;
        roomout = n2;
    }
    
    void Print() {
        cout << "[" << roomin << ", " << roomout << "]";
    }
};

// list of connection data class
class RoomConnectionList : public vector<RoomConnection> {
  public:
    void push_back(RoomConnection rc) {
        vector<RoomConnection>::push_back(rc);
    }
    void push_back(int r1, int r2) {
        RoomConnection rc(r1 ,r2);
        push_back(rc);
    }
    
    void Print() {
        cout << "Room Connection List : " << size() << endl;
        for (vector<RoomConnection>::iterator it = begin(); it != end(); it++) {
            if (it != begin()) {
                cout << " ";
            }
            it->Print();
        }
        cout << endl;
    }
    
    // delete redundant connection
    // (if connection has duplicate data, result has also duplication)
    // eg. {1,2} {2,3} {1,2} {2,1} --> {1,2} {2,3}
    void Unique() {
        vector<RoomConnection>::iterator it, itstart, itend;
        for (it = begin(); it != end(); it++) {
            if (it->roomin > it->roomout) {
                std::swap(it->roomin, it->roomout);
            }
        }
        sort(begin(), end(), SortCmp);
        itstart = begin();
        itend =  unique(begin(), end(), UniqueCmp);
        assign(itstart, itend);
    }
    
  private:
    static bool SortCmp(RoomConnection a1, RoomConnection a2) {
        if (a1.roomin > a2.roomin) {
            return false;
        } else if (a1.roomin == a2.roomin) {
            if (a1.roomout > a2.roomout) {
                return false;
            }
        }
        return true;
    }
    static bool UniqueCmp(RoomConnection a1, RoomConnection a2) {
        if ((a1.roomin == a2.roomin) && (a1.roomout == a2.roomout)) {
            return true;
        }
        return false;
    }
};

// individual route class
class Route : public vector<int> {
  public:
    int Exist(int room) {
        for (vector<int>::iterator it = begin(); it != end(); it++) {
            if (*it == room) {
                return 1;
            }
        }
        return 0;
    }
    
    void Print() {
        cout << "[";
        for (vector<int>::iterator it = begin(); it != end(); it++) {
            if (it != begin()) {
                cout << ", ";
            }
            cout << *it;
        }
        cout << "]";
    }
};

// list of route class
class RouteList : public vector<Route> {
  public:
    void PrintMinimumRoute() {
        if (!size()) {
            cout << "No minimum route." << endl;
            return;
        }
        int minDistance = INT_MAX;
        for (vector<Route>::iterator it = begin(); it != end(); it++) {
            int size = (*it).size();
            minDistance = min(minDistance, size - 1);
        }
        cout << "Minimum Distance : " << minDistance << endl;
        cout << "--------------------------------" << endl;
        
        int numMinRoute = 0;
        for (vector<Route>::iterator it = begin(); it != end(); it++) {
            int size = (*it).size();
            if ((size - 1) == minDistance) {
                it->Print();
                cout << endl;
                numMinRoute++;
            }
        }
        cout << numMinRoute << " route found." << endl;
    }
    
    void Print() {
        cout << "All route" << endl;
        cout << "--------------------------------" << endl;
        for (vector<Route>::iterator it = begin(); it != end(); it++) {
            it->Print();
            cout << endl;
        }
    }
};

// find route with recursive
void FindRoute(RoomConnectionList *conList, int roomEnd, Route *route, RouteList *routeList)
{
    int lastRoom = route->back();
    int nextRoom;
    vector<RoomConnection>::iterator it;
    
    for (it =  conList->begin(); it != conList->end(); it++) {
        nextRoom = 0;
        if (it->roomin == lastRoom) {
            nextRoom = it->roomout;
        } else if (it->roomout == lastRoom) {
            nextRoom = it->roomin;
        }
        
        if (nextRoom) {
            if (!route->Exist(nextRoom)) { // avoid loop (back to same room?)
                Route tempRoute = *route;
                tempRoute.push_back(nextRoom);
                if (nextRoom == roomEnd) { // reach end room then add to list.
                    routeList->push_back(tempRoute);
                } else {
                    FindRoute(conList, roomEnd, &tempRoute, routeList);
                }
            }
        }
    }
}

// find all route (entry)
void FindAllRoute(RoomConnectionList *conList, int roomStart, int roomEnd, RouteList *routeList)
{
    Route tempRoute;
    
    tempRoute.clear();
    tempRoute.push_back(roomStart);
    FindRoute(conList, roomEnd, &tempRoute, routeList);
}

// main 
int main(void)
{
    RoomConnectionList roomConnection;
    RouteList route;
    
    // Room Connection List.
    roomConnection.push_back(1,2);
    roomConnection.push_back(1,3);
    roomConnection.push_back(1,4);
    roomConnection.push_back(2,5);
    roomConnection.push_back(3,5);
    roomConnection.push_back(4,5);
    roomConnection.push_back(2,6);
    roomConnection.push_back(3,6);
    roomConnection.push_back(4,6);
    roomConnection.push_back(5,7);
    roomConnection.push_back(6,7);
    
    int roomStart = 1;                // start room No.
    int roomEnd   = 7;                // end room No.
    
    roomConnection.Print();
    
    // check connection list (delete redundant connection)
    roomConnection.Unique();
    
    // find all route
    FindAllRoute(&roomConnection, roomStart, roomEnd, &route);
    
    // print result
    cout << "Start Room : " << roomStart << endl;
    cout << "End   Room : " << roomEnd << endl;
    cout << "There are " << route.size() << " different route." << endl;
    cout << endl;
    
    // print minimum distance
    route.PrintMinimumRoute();
    
    // print all route (for debug)
    //cout << endl << endl;
    //route.Print();
    
    return 0;
}