def dfs_search_recursive(G, src):
    """
    Apply Depth First Search to a graph from src. Return
    dictionary of explored trail.
    Performance is O(N+E) since every edge is visited once for a directed
    graph and twice for an undirected graph.
    Warning: This code is likely to cause a RecursionError when applied
    to a graph with thousands of nodes, because Python sets the recursion
    limit to about 1000.
    """
    marked = {}
    node_from = {}

    def dfs(v):
        marked[v] = True
        for w in G[v]:
            if not w in marked:
                node_from[w] = v
                dfs(w)
    dfs(src)
    return node_from