def validate_graph(graph, weighted=False, nonnegative=False):
    if not isinstance(graph, dict):
        raise ValueError("Expected an adjacency dictionary")
    if any(not isinstance(vertex, str) for vertex in graph):
        raise ValueError("String vertex labels required")
    for vertex, neighbors in graph.items():
        for edge in neighbors:
            if weighted:
                target, weight = edge
                if type(weight) is not int or (nonnegative and weight < 0):
                    raise ValueError("Invalid integer edge weight")
            else:
                target = edge
            if target not in graph:
                raise ValueError("Unknown target vertex")

def dfs(graph, start):
    validate_graph(graph)
    if start not in graph:
        raise ValueError("Unknown start vertex")
    seen, order = {start}, [start]
    pending = [iter(graph[start])]
    while pending:
        try:
            target = next(pending[-1])
        except StopIteration:
            pending.pop()
            continue
        if target not in seen:
            seen.add(target)
            order.append(target)
            pending.append(iter(graph[target]))
    return order

print(dfs({"gate": ["oak", "pond"], "oak": ["shed"], "pond": ["shed"], "shed": [], "hill": []}, "gate"))