def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first
    [2nd Edition: p 75, 3rd Edition: p 87]

    Your search algorithm needs to return a list of actions that reaches
    the goal.  Make sure to implement a graph search algorithm
    [2nd Edition: Fig. 3.18, 3rd Edition: Fig 3.7].

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print "Start:", problem.getStartState()
    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    print "Start's successors:", problem.getSuccessors(problem.getStartState())
    """
    "*** YOUR CODE HERE ***"
    from util import Stack
    lastSibling = 0
    frontierStack = Stack()
    startState = problem.getStartState()
    exploredSet = set()
    frontierSet = set()
    solutionList = []
    exploredSet.add(startState)
    successorList = problem.getSuccessors(startState)
    if len(successorList) > 1:
        lastSibling = 0
    else:
        lastSibling = lastSibling + 1
    for successor in successorList:
        frontierStack.push(successor)
        frontierSet.add(successor[0])
    while not frontierStack.isEmpty():
        leafNode = frontierStack.pop() #leafNode of form(state, direc, cost)
        solutionList.append(leafNode[1])
        #print "FrontierStack:", frontierStack.list
        frontierSet.remove(leafNode[0])
        #print "frontierSet:", frontierSet
        if problem.isGoalState(leafNode[0]):
            return solutionList
        exploredSet.add(leafNode[0])
        successorList = problem.getSuccessors(leafNode[0])
        #print "Successor List Before:", successorList
        #print "Explored Set:", exploredSet
        #print "Frontier Set:", frontierSet
        for successor in successorList[:]:
            if (successor[0] in exploredSet) or (successor[0] in frontierSet):
                successorList.remove(successor)
                #print "HOW OFTEN DO I HAPPEN"
        if (len(successorList) > 1):
            print "CHECK POINT UNO"
            lastSibling = 0
        else:
            lastSibling = lastSibling + 1
            print "CHECK POINT DOS"
        print lastSibling
        #print "Solution List:", solutionList
        print "Current leaf:", leafNode
        print "Successor List:", successorList
        #print "Length Successor List:", len(successorList)
        if (len(successorList) is 0):
            #print "Now that we're here, lastSibling is:", lastSibling
            while lastSibling > 0:
                #print "WHOOOSH!"
                solutionList.pop()
                lastSibling = lastSibling - 1
            #print "Dead end, so pop one. Solution List:", solutionList
        for successor in successorList:
            if(successor[0] not in exploredSet) and (successor[0] not in frontierSet):
                frontierStack.push(successor)
                frontierSet.add(successor[0])
        #print "FrontierStack After:", frontierStack.list
    return "Failure"