#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <iostream>
#include <string>
#include <sstream>

template< typename T, typename REF = T >
using adjacency_list_t = std::unordered_map< T, std::unordered_set<REF> > ;

using adjacency_list = adjacency_list_t<int> ;

// input of pairs of adjacent vertices of a directed graph
// 1 7 => edge from 1 -------> 7
// 2 7 => edge from 2 -------> 7
// 1 5 => edge from 1 -------> 5
// etc.

adjacency_list make_adjacency_list( std::istream& stm )
{
    adjacency_list graph ;
    int a, b ;
    while( stm >> a >> b ) { graph[a].insert(b) ; graph[b] ; }
    return graph ;
}

template< typename STACK_OR_QUEUE, typename FN_NEXT >
bool graph_search( const adjacency_list& graph, int start, int target, FN_NEXT next )
{
    STACK_OR_QUEUE stk_or_queue ;
    std::unordered_set<int> visited ;
    stk_or_queue.push(start) ;
    while( !stk_or_queue.empty() )
    {
        int id =  next(stk_or_queue) ;
        std::cout << id << ' ' ;
        visited.insert(id) ;
        if( id == target ) { std::cout << " <= target\n" ; return true ; }
        else
        {
            stk_or_queue.pop() ;
            auto iter = graph.find(id) ;
            if( iter != graph.end() )
                for( auto& n : iter->second )
                    if( visited.find(n) == visited.end() ) stk_or_queue.push(n) ;
        }
    }
    std::cout << "  could not find target\n" ;
    return false ;
}

bool depth_first_search( const adjacency_list& graph, int start, int target )
{
    using stack = std::stack<int> ;
    return graph_search<stack>( graph, start, target, []( stack& s ) { return s.top() ; } ) ;
}

bool breadth_first_search( const adjacency_list& graph, int start, int target )
{
    using queue = std::queue<int> ;
    return graph_search<queue>( graph, start, target, []( queue& q ) { return q.front() ; } ) ;
}

int main()
{
    const std::string str = "1 2   1 7   1 8   2 3   2 6   2 10  3 4   3 5   3 11   "
                            "6 10   6 12  8 9   8 12   9 10   9 11   11 7   12 5" ;
    std::istringstream stm(str) ;
    const adjacency_list graph = make_adjacency_list(stm) ;

    std::cout << "DFS 1 to 5 => " ; depth_first_search( graph, 1, 5 ) ;
    std::cout << "BFS 1 to 5 => " ; breadth_first_search( graph, 1, 5 ) ;
    std::cout << "DFS 1 to 12 => " ; depth_first_search( graph, 1, 12 ) ;
    std::cout << "BFS 1 to 12 => " ; breadth_first_search( graph, 1, 12 ) ;
}