from game import Directions

    fringe = util.Stack()
    expanded = []

    fringe.push(problem.getStartState())

    while (not fringe.isEmpty()):
        toExpand = fringe.pop()

        if (toExpand in expanded):
            print "NOTEXPANDING: ", toExpand, "lenToExpand:" , len(toExpand)
            continue;
        else:

            if len(toExpand) == 2:
                if (problem.isGoalState(toExpand)):
                    print "GOAL STATE FOUND"
                    break
            else:
                if (problem.isGoalState(toExpand[0])):
                    print "GOAL STATE FOUND"
                    break

            expanded.append(toExpand)

            print "toExpand: ", toExpand, "lenToExpand:" , len(toExpand)
            if len(toExpand) == 2:
                for i in reversed(problem.getSuccessors(toExpand)):
                    fringe.push(i)
            else:
                for i in reversed(problem.getSuccessors(toExpand[0])):
                    fringe.push(i)