@Override
  public StateDist search() {
    stateDistMap.clear();
    statesWithUnexploredNodes = new HashMap<>();

    SearchState initialState = getInitialState();
    maxDist = h.estimateCostToGoal(initialState);
    statesWithUnexploredNodes.put(initialState, 0);
    while (true) {
      for (SearchState state : statesWithUnexploredNodes.keySet()) {
        stateDistMap.remove(state);
      }
      HashMap<SearchState, Integer> tmp = statesWithUnexploredNodes;
      statesWithUnexploredNodes = new HashMap<>();
      int newMaxDist = OO;
      for (Entry<SearchState, Integer> state : tmp.entrySet()) {
        StateDist result = limitDfs(state.getKey(), state.getValue(), maxDist);
        if (result == null)
          continue;
        if (result.state != null)
          return result;
        newMaxDist = Math.min(newMaxDist, result.dist);
      }
      System.out.println("Dist: " + maxDist + " size: " + stateDistMap.size() + " unexplored: " + statesWithUnexploredNodes.size());
      if (newMaxDist >= OO)
        return null;
      maxDist = newMaxDist;
    }
  }