Order Recipe Prep Steps Into the Smallest Valid Sequence

A recipe app stores each dish's prep steps as named strings, along with a list of ordering constraints of the form "step A must happen before step B". Some steps have no prerequisites at all, and some steps aren't connected by any constraint to the rest of the dish (e.g. "preheat oven" can happen anytime). Implement a function that returns one valid ordering of all the steps — one that respects every constraint — and, among all valid orderings, returns the one that is lexicographically smallest by step name, so the result is fully deterministic regardless of how the steps or constraints were listed.

def order_steps(steps: list[str], prerequisites: list[tuple[str, str]]) -> list[str] | None:
    """
    steps: every step name that must appear exactly once in the result.
    prerequisites: each (a, b) means a must appear before b in the result.
    Returns the lexicographically smallest valid ordering, or None if the
    constraints are contradictory (a cycle exists).
    """

Example

steps = ['wash', 'chop', 'boil', 'plate', 'season', 'garnish']
prerequisites = [
    ('wash', 'chop'),
    ('chop', 'boil'),
    ('boil', 'plate'),
    ('season', 'plate'),
]

order_steps(steps, prerequisites)
-> ['garnish', 'season', 'wash', 'chop', 'boil', 'plate']

garnish has no constraints at all, and season has no prerequisite of its own, so both are free to go first; between them, and ahead of wash (which also starts with no prerequisite), the lexicographically smallest choice at every step is what picks garnish, then season, then wash.

Constraints

• Up to 10,000 steps and 50,000 prerequisite pairs.
• A step listed in steps but mentioned in no prerequisite pair must still appear in the result.
• If the prerequisites contain a cycle, return None rather than a partial or arbitrary ordering.