def ids(problem, stype):
    """
    Iterative deepening depth-first search
    :param problem: problem
    :param stype: type of search: graph or tree (dls_gs or dls_ts)
    :return: (path, stats): solution as a path and stats
    The stats are a tuple of (time, npexp, maxdepth): elapsed time, number of expansions, max depth reached
    """
    cutoff = True
    depth  = 0
    time   = 0.0
    globals()["expc"] = 0
    while True:
        solution, cutoff_result, stats = stype(problem, depth)
        depth += 1
        time  += stats[0]
        if cutoff_result != cutoff:
            return solution, (time, stats[1], stats[2])